好数字

GitHub跳转原题关系图返回列表

用背包 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

形式化题目

给定正整数 nn 与数字集合 S⊆{0,1,…,9}S \subseteq \{0, 1, \dots, 9\},求长度为 2n2n 的序列 a1a2⋯a2na_1 a_2 \cdots a_{2n} 的个数(每位 ai∈Sa_i \in S,允许前导 00),满足

∑i=1nai=∑i=n+12nai或者∑k=1na2k−1=∑k=1na2k\sum_{i=1}^{n} a_i = \sum_{i=n+1}^{2n} a_i \quad \text{或者} \quad \sum_{k=1}^{n} a_{2k-1} = \sum_{k=1}^{n} a_{2k}

答案对 999983999983 取模。数据范围:n⩽1000n \leqslant 1000,∣S∣⩽10|S| \leqslant 10。

记两个事件为

  • AA:前 nn 位之和 LL 等于后 nn 位之和 RR;
  • BB:奇数位之和 OO 等于偶数位之和 EE。

要求的就是 ∣A∪B∣|A \cup B|。

正解

思路

暴力为什么不行。 直接枚举 2n2n 位有 ∣S∣2n|S|^{2n} 种填法,n=1000n = 1000 时是天文数字。就算用容斥 ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|,若想一次 DP 同时记录 L,R,O,EL, R, O, E 四个量,状态是四维的,同样不可承受。突破口在于:这四组和的约束高度退化,可以解耦成彼此独立的两两相等。

单事件 ∣A∣|A| 的计数。 L,RL, R 各自只依赖前 nn 位、后 nn 位,两段彼此独立。设

f(k,s)=#{用 S 中数字构成 k 位,数位和恰为 s}f(k, s) = \#\{\text{用 } S \text{ 中数字构成 } k \text{ 位,数位和恰为 } s\}

则先定前 nn 位和为 ss(f(n,s)f(n, s) 种),后 nn 位和也必须为 ss(f(n,s)f(n, s) 种),于是

∣A∣=∑sf(n,s)2|A| = \sum_s f(n, s)^2

BB 只是把「前 nn 位 / 后 nn 位」换成「奇数位 / 偶数位」,各 nn 个位置,是同一件事,故 ∣B∣=∣A∣|B| = |A|。

交集 ∣A∩B∣|A \cap B| 的解耦(本题关键)。 把 2n2n 位按「前半 / 后半」与「奇数位 / 偶数位」切成四组:

组 位置 个数 和
1 前 nn 位中的奇数位 m1=⌈n/2⌉m_1 = \lceil n/2 \rceil s1s_1
2 前 nn 位中的偶数位 m2=⌊n/2⌋m_2 = \lfloor n/2 \rfloor s2s_2
3 后 nn 位中的奇数位 m3m_3 s3s_3
4 后 nn 位中的偶数位 m4m_4 s4s_4

四个组的位置个数是确定的:区间 [1,n][1, n] 内的奇数下标有 ⌈n/2⌉\lceil n/2 \rceil 个(组 1),偶数下标有 ⌊n/2⌋\lfloor n/2 \rfloor 个(组 2);区间 [n+1,2n][n+1, 2n] 内的偶数下标有 n−⌊n/2⌋=⌈n/2⌉n - \lfloor n/2 \rfloor = \lceil n/2 \rceil 个(组 4),奇数下标有 ⌊n/2⌋\lfloor n/2 \rfloor 个(组 3)。也就是无论 nn 奇偶都有 m1=m4=⌈n/2⌉m_1 = m_4 = \lceil n/2 \rceil、m2=m3=⌊n/2⌋m_2 = m_3 = \lfloor n/2 \rfloor(可直接代入 n=2n = 2、n=3n = 3 各数一遍验证)。

两条条件分别写成

L=R  ⟺  s1+s2=s3+s4,O=E  ⟺  s1+s3=s2+s4L = R \iff s_1 + s_2 = s_3 + s_4, \qquad O = E \iff s_1 + s_3 = s_2 + s_4

两式相减,消掉 s1,s4s_1, s_4:

(s1+s2)−(s1+s3)=(s3+s4)−(s2+s4)  ⟹  s2−s3=s3−s2  ⟹  2(s2−s3)=0(s_1 + s_2) - (s_1 + s_3) = (s_3 + s_4) - (s_2 + s_4) \implies s_2 - s_3 = s_3 - s_2 \implies 2(s_2 - s_3) = 0

在整数上 s2=s3s_2 = s_3,代回任一式得 s1=s4s_1 = s_4。反过来若 s1=s4s_1 = s_4 且 s2=s3s_2 = s_3,两式显然成立。于是

L=R ∧ O=E  ⟺  s1=s4 ∧ s2=s3L = R \ \wedge\ O = E \iff s_1 = s_4 \ \wedge\ s_2 = s_3

这一步让问题彻底解耦:组 1 与组 4 各有 m1=⌈n/2⌉m_1 = \lceil n/2 \rceil 个位置、只要求和相等,组 2 与组 3 各有 m2=⌊n/2⌋m_2 = \lfloor n/2 \rfloor 个位置、只要求和相等,而这两对位置互不相交、互不约束。所以

∣A∩B∣=(∑uf(m1,u)2)⋅(∑vf(m2,v)2)|A \cap B| = \Big(\sum_u f(m_1, u)^2\Big) \cdot \Big(\sum_v f(m_2, v)^2\Big)

答案。 由容斥

Ans=(2∣A∣−∣A∩B∣) mod 999983\text{Ans} = \big(2|A| - |A \cap B|\big) \bmod 999983

举 n=2,S={1,2}n = 2, S = \{1, 2\} 复核:f(1,⋅)f(1, \cdot) 在 s=1,2s = 1, 2 处为 11;f(2,1)=1,f(2,2)=2,f(2,3)=1f(2, 1) = 1, f(2, 2) = 2, f(2, 3) = 1,∑sf(2,s)2=1+4+1=6\sum_s f(2, s)^2 = 1 + 4 + 1 = 6。m1=m2=1m_1 = m_2 = 1,f(1,⋅)f(1, \cdot) 的平方和 =12+12=2= 1^2 + 1^2 = 2,交集 =2×2=4= 2 \times 2 = 4,答案 =2×6−4=8= 2 \times 6 - 4 = 8,与题面「合法的好数字有 88 个」以及列出的 1111,1122,1212,1221,2112,2121,2211,22221111, 1122, 1212, 1221, 2112, 2121, 2211, 2222 完全一致。再看题面样例 n=2n = 2、S={0,1,…,9}S = \{0, 1, \dots, 9\}(输入串 0987654321):用 22 个数字凑出和 ss 的方案数依次是 1,2,…,9,10,9,…,11, 2, \dots, 9, 10, 9, \dots, 1(s=0…18s = 0 \dots 18),故 ∑sf(2,s)2=2(12+⋯+92)+102=570+100=670\sum_s f(2, s)^2 = 2(1^2 + \dots + 9^2) + 10^2 = 570 + 100 = 670;而 ∑sf(1,s)2=10\sum_s f(1, s)^2 = 10,交集 =10×10=100= 10 \times 10 = 100;答案 =2×670−100=1240= 2 \times 670 - 100 = 1240,与【输出样例】完全一致。

代码

python
#!/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」写成多项式幂:f(k,⋅)f(k, \cdot) 的生成函数正是 (∑d∈Sxd)k\big(\sum_{d \in S} x^d\big)^k,而多项式乘法可以用大整数乘法打包完成(每个系数占 8 字节的槽,槽内不进位),于是 O(n2)O(n^2) 的 DP 变成几次快速幂里的整数乘法,n=1000n = 1000 时在 CPython 里也是瞬间出结果。按背包 DP 逐位递推的 C++ 完整版本:

cpp
/**
 * 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 按位递推,第 kk 位枚举 9k9k 个和、每个和枚举 ∣S∣|S| 个数字,总计 O(n⋅9n⋅∣S∣)≈9×107O(n \cdot 9n \cdot |S|) \approx 9 \times 10^7 次基本运算,n=1000n = 1000 时轻松跑进 1000 ms1000 \text{ ms}。
  • 空间:只保留三个快照(f(⌈n/2⌉,⋅)f(\lceil n/2 \rceil, \cdot)、f(⌊n/2⌋,⋅)f(\lfloor n/2 \rfloor, \cdot)、f(n,⋅)f(n, \cdot))加一个滚动数组,O(9n)O(9n) 个 int,约 3636 KB,远小于 128128 MB。
  • Python 版把 DP 换成多项式快速幂 + 大整数卷积,复杂度降为 O(nlog⁡n)O(n \log n) 量级的整数乘法,空间同为 O(9n)O(9n)。

总结

本题的骨架是「容斥 + 背包计数」,但真正的难点在交集。把 2n2n 位按前后半、奇偶位切成四组后,两条线性条件相减就逼出 s2=s3s_2 = s_3、s1=s4s_1 = s_4,原本耦合的四维约束退化成两组互不相干的「等长序列和相等」。于是整道题只剩一个原语:给定段长 kk,求两段 kk 位数位和相等的配对数 ∑sf(k,s)2\sum_s f(k, s)^2。这个原语由数位和分布 f(k,s)f(k, s) 的 0/10/1 背包给出,答案就是

2∑sf(n,s)2−(∑uf(⌈n/2⌉,u)2)(∑vf(⌊n/2⌋,v)2)(mod999983)2\sum_s f(n, s)^2 - \Big(\sum_u f(\lceil n/2 \rceil, u)^2\Big)\Big(\sum_v f(\lfloor n/2 \rfloor, v)^2\Big) \pmod{999983}

实现上要注意三点:集合要去重(题面给的是「集合」);nn 为奇数时 ⌈n/2⌉≠⌊n/2⌋\lceil n/2 \rceil \neq \lfloor n/2 \rfloor,快照别混;n=1n = 1 时 ⌊n/2⌋=0\lfloor n/2 \rfloor = 0,f(0,0)=1f(0, 0) = 1 的退化情形要显式处理。

数据说明

本题素材源(new_ROJ/problems/1778/)附带了数据生成脚本 data.py,说明 data/ 是按题面重建的自造数据、题面本身也是网络重建,与官方一本通原题的口径可能存在偏差,使用数据时需留意。数据生成脚本用了一套解析可证的锚点(∣S∣=1|S| = 1 时答案恒为 11;n=1n = 1 时答案 =∣S∣= |S|)加题面给定的两个锚点(n=2,S={0,…,9}→1240n=2, S=\{0,\dots,9\} \to 1240;n=2,S={1,2}→8n=2, S=\{1,2\} \to 8),其余点(n=7,100,500,999,1000n = 7, 100, 500, 999, 1000)的期望值只是标程输出的回归锚点,并非独立复算。本次交付用独立写的暴力枚举(枚举 2n2n 位、直接判定两条件)在 n⩽4n \leqslant 4、六种集合上复核了本题解法与题面定义一致(含 n=2,S={1,2}→8n=2,S=\{1,2\} \to 8),并让 main.cpp、main.py 逐点跑过 data/ 的全部 1010 个点,均与 .out 相同。

图示解析

下图画出 n=2n = 2、S={1,2}S = \{1, 2\} 时四组位置的配对关系:组 1 与组 4 各 m1=1m_1 = 1 个位置配对(和相等),组 2 与组 3 各 m2=1m_2 = 1 个位置配对,两对彼此独立。

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

当 n=2n = 2 时 L=a1+a2L = a_1 + a_2、R=a3+a4R = a_3 + a_4、O=a1+a3O = a_1 + a_3、E=a2+a4E = a_2 + a_4,两条件相减立刻得到 a2=a3a_2 = a_3,再代回得 a1=a4a_1 = a_4——正是上图两条独立配对边。于是交集计数 == (a1=a4a_1 = a_4 的选法数)×\times(a2=a3a_2 = a_3 的选法数)=(∑uf(1,u)2)2=4= (\sum_u f(1,u)^2)^2 = 4(S={1,2}S = \{1,2\} 时)。