用背包 DP 统计数位和分布 f[k][s],容斥后答案 = 2Σf[n][s]² − Σf[⌈n/2⌉][s]² · Σf[⌊n/2⌋][s]²。
OJ: roj
题目 ID: 1778
难度:提高+/省选-
标签:动态规划容斥原理背包计数python
创建: 2026-10-08 02:12
更新: 2026-10-08 02:12
形式化题目
给定正整数
答案对
记两个事件为
:前 位之和 等于后 位之和 ; :奇数位之和 等于偶数位之和 。
要求的就是
正解
思路
暴力为什么不行。 直接枚举
单事件
则先定前
交集
| 组 | 位置 | 个数 | 和 |
|---|---|---|---|
| 1 | 前 |
||
| 2 | 前 |
||
| 3 | 后 |
||
| 4 | 后 |
四个组的位置个数是确定的:区间
两条条件分别写成
两式相减,消掉
在整数上
这一步让问题彻底解耦:组 1 与组 4 各有
答案。 由容斥
举 0987654321):用
代码
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 02:12
# update_at: 2026-10-08 02:12
import sys
MOD = 999983 # 题目要求的取模值
SLOT = 8 # 每个系数占的字节数:系数 < 2^20,卷积和 < 2^53,槽之间不会进位串扰
# 把多项式打包成一个大整数:第 s 个槽(SLOT 字节,即第 s·SLOT·8 位)存 x^s 的系数。
# 于是「两个多项式相乘」等价于「两个大整数相乘」,整条卷积由 CPython 的大整数乘法一次算完。
type Poly = tuple[int, int] # (打包后的大整数, 次数上界)
def mul(a: Poly, b: Poly) -> Poly:
"""多项式乘法:大整数相乘得到全部卷积和,再逐槽取模压回。"""
packed, deg = a[0] * b[0], a[1] + b[1]
body = packed.to_bytes((deg + 1) * SLOT, "little")
slots = (int.from_bytes(body[i:i + SLOT], "little") % MOD for i in range(0, len(body), SLOT))
return int.from_bytes(b"".join(s.to_bytes(SLOT, "little") for s in slots), "little"), deg
def power(base: Poly, e: int) -> Poly:
"""快速幂:返回 base 的 e 次幂多项式。"""
result: Poly = (1, 0) # 常数多项式 1,即「0 位、数位和为 0 的方案数为 1」
squares = base
while e:
if e & 1:
result = mul(result, squares)
e >>= 1
if e:
squares = mul(squares, squares)
return result
def same_sum_pairs(poly: Poly) -> int:
"""Σ_s c_s² mod MOD:两段 k 位序列「数位和相等」的配对方案数。
系数 c_s 表示「用 S 中数字构成 k 位、数位和为 s」的方案数;两段各自独立取数,
只需数位和相同,故配对方案数恰为系数平方和。
"""
packed, deg = poly
body = packed.to_bytes((deg + 1) * SLOT, "little")
return sum(int.from_bytes(body[i:i + SLOT], "little") ** 2
for i in range(0, len(body), SLOT)) % MOD
def count_good(base: Poly, n: int) -> int:
"""按容斥公式计数:2·S(P^n) − S(P^⌈n/2⌉)·S(P^⌊n/2⌋),其中 P = Σ_{d∈S} x^d,S 即 same_sum_pairs。"""
half = power(base, n // 2) # P^⌊n/2⌋
odd = mul(half, base) if n % 2 else half # P^⌈n/2⌉
whole = mul(half, odd) # P^n = P^⌊n/2⌋ · P^⌈n/2⌉
# 前 n 位之和 = 后 n 位之和、奇数位之和 = 偶数位之和 两个事件的方案数相同(均为 S(P^n));
# 交集由「s1 = s4 且 s2 = s3」解耦,等于两个独立配对的乘积。
return (2 * same_sum_pairs(whole) - same_sum_pairs(odd) * same_sum_pairs(half)) % MOD
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
n = int(next(data))
given = next(data) # 题面给的长度不超过 10 的字符串
digits = sorted({ch - 48 for ch in given}) # 去重:题面说的是「数字集合」
base: Poly = (sum(1 << (d * SLOT * 8) for d in digits), max(digits)) # Σ_{d∈S} x^d
print(count_good(base, n))
if __name__ == "__main__":
solve()Python 版本用的是同一套公式,但把「背包 DP」写成多项式幂:
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 02:12
* update_at: 2026-10-08 02:12
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 999983; // 题目要求的取模值
const int MAXN = 1000; // n 的上限
const int MAXS = 9 * MAXN + 1; // 各位数字和的上限:最多 n 位、每位最大 9
// f[s] = 用 S 中数字构成 k 位数、各位数字和恰为 s 的方案数(mod MOD)
// 滚动推进 k:cur 是 f[k],nxt 是 f[k+1]。值域 < 999983 < 2^20,int 够用
int cur[MAXS];
int nxt[MAXS];
int fn[MAXS]; // 快照 f[n][*]
int f1[MAXS]; // 快照 f[l1][*],l1 = ceil(n/2)
int f2[MAXS]; // 快照 f[l2][*],l2 = floor(n/2)
int dig[16]; // 集合 S 里的数字(已去重,按输入顺序)
int digCnt; // |S|
// 返回 sum_s f[s]^2 mod MOD:即「两段各 k 位、数字和相等的方案数」
ll square_sum(const int* f, int lim) {
ll res = 0;
for (int s = 0; s <= lim; s++) {
res = (res + (ll)f[s] * f[s]) % MOD;
}
return res;
}
int main() {
ll n;
if (scanf("%lld", &n) != 1) return 0;
char str[64];
if (scanf("%63s", str) != 1) return 0;
// 集合去重:题面给的是「数字集合」,重复字符只算一个数字
bool used[10] = {false};
int len = strlen(str);
for (int i = 0; i < len; i++) {
int d = str[i] - '0';
if (!used[d]) {
used[d] = true;
dig[digCnt++] = d;
}
}
// 前 n 位里奇数位有 l1 个、偶数位有 l2 个(n 为奇数时 l1 = l2 + 1)
ll l1 = (n + 1) / 2;
ll l2 = n / 2;
memset(cur, 0, sizeof(cur));
cur[0] = 1; // f[0][0] = 1:0 位、和为 0 的方案数为 1
// 规模为 0 的快照(n = 1 时 l2 = 0 会用到)
if (l2 == 0) memcpy(f2, cur, sizeof(f2));
if (l1 == 0) memcpy(f1, cur, sizeof(f1));
// 背包计数:每加一位,就枚举集合里的数字做一次转移
for (ll k = 1; k <= n; k++) {
int lim = 9 * (int)k; // k 位的数字和不会超过 9k
memset(nxt, 0, sizeof(int) * (lim + 1));
for (int s = 0; s <= lim; s++) {
ll acc = 0;
for (int j = 0; j < digCnt; j++) {
int d = dig[j];
if (s - d >= 0) acc += cur[s - d];
}
nxt[s] = (int)(acc % MOD);
}
memcpy(cur, nxt, sizeof(int) * (lim + 1)); // 滚动到第 k 位
if (k == l1) memcpy(f1, cur, sizeof(f1));
if (k == l2) memcpy(f2, cur, sizeof(f2));
if (k == n) memcpy(fn, cur, sizeof(fn));
}
// 前 n 位之和 = 后 n 位之和的方案数,与奇数位之和 = 偶数位之和的方案数同为 A
ll A = square_sum(fn, 9 * (int)n);
// 交集:s1 = s4 且 s2 = s3,两组位置各自独立,方案数相乘
ll inter = square_sum(f1, 9 * (int)l1) * square_sum(f2, 9 * (int)l2) % MOD;
ll ans = (2 * A % MOD - inter % MOD + MOD) % MOD;
printf("%lld\n", ans);
return 0;
}复杂度
- 时间:背包 DP 按位递推,第
位枚举 个和、每个和枚举 个数字,总计 次基本运算, 时轻松跑进 。 - 空间:只保留三个快照(
、 、 )加一个滚动数组, 个 int,约KB,远小于 MB。 - Python 版把 DP 换成多项式快速幂 + 大整数卷积,复杂度降为
量级的整数乘法,空间同为 。
总结
本题的骨架是「容斥 + 背包计数」,但真正的难点在交集。把
实现上要注意三点:集合要去重(题面给的是「集合」);
数据说明
本题素材源(new_ROJ/problems/1778/)附带了数据生成脚本 data.py,说明 data/ 是按题面重建的自造数据、题面本身也是网络重建,与官方一本通原题的口径可能存在偏差,使用数据时需留意。数据生成脚本用了一套解析可证的锚点(main.cpp、main.py 逐点跑过 data/ 的全部 .out 相同。
图示解析
下图画出
flowchart LR
subgraph P1["组 1:前 n 位奇数位(m1 = 1 个)"]
A1["a₁"]
end
subgraph P2["组 2:前 n 位偶数位(m2 = 1 个)"]
A2["a₂"]
end
subgraph P3["组 3:后 n 位奇数位(m2 = 1 个)"]
A3["a₃"]
end
subgraph P4["组 4:后 n 位偶数位(m1 = 1 个)"]
A4["a₄"]
end
A1 == "s1 = s4" ==> A4
A2 == "s2 = s3" ==> A3
当