多项式相乘

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

把展开式的字符拆成单项式与结构两部分,用对称性把前者求和成 2^(n-1)(n+D),化简得闭形式 O(log n) 求解。

OJ: roj

题目 ID: 1811

难度:普及+/提高-

标签:数学组合数学快速幂python

创建: 2026-10-08 04:55

更新: 2026-10-08 04:55

形式化题目

给定正整数 nn,把

(x+a1)(x+a2)⋯(x+an−1)(x+an)(x+a_1)(x+a_2)\cdots(x+a_{n-1})(x+a_n)

按题面规定的写法完整展开成一行文本,统计这行文本的总字符数 tt,输出 t mod 10000t \bmod 10000。

题面规定的写法(以 n=3n=3 为例):

x3+x2(a1+a2+a3)+x(a1a2+a1a3+a2a3)+a1a2a3x^3+x^2(a_1+a_2+a_3)+x(a_1a_2+a_1a_3+a_2a_3)+a_1a_2a_3

即按 xx 的次数 kk 从 nn 降到 00 排列:

  • k=nk=n(最高次):只写 xnx^n,省略系数 11、不带括号;n=1n=1 时写作 xx。
  • 1⩽k⩽n−11 \leqslant k \leqslant n-1(中间项):写作 xkx^k 后面紧跟一对括号, 括号里是 (nn−k)\binom{n}{n-k} 个“n−kn-k 个 aa 相乘”的单项式,用 + 连接;k=1k=1 时指数 11 不写。
  • k=0k=0(常数项):只有 a1a2⋯ana_1a_2\cdots a_n 一个单项式,不写 xx、不带括号。

计长规则:x、a、(、)、+ 每个计 11 个字符;指数的每个数字计 11; 下标的每个数字计 11(a12a_{12} 的下标 1212 占 22 个字符)。 注意脱字符 ^ 不在题面枚举的计数字符里,不计长度。

于是答案依赖两个量:nn 本身,以及

D=∑i=1nd(i),d(i)=整数 i 的十进制位数D=\sum_{i=1}^{n} d(i), \qquad d(i)=\text{整数 } i \text{ 的十进制位数}

(DD 是全部下标数字的总个数)。数据范围 n⩽109n \leqslant 10^9,答案  mod  10000\bmod\ 10000。

正解

思路

朴素做法。 按定义逐项拼接字符串,依次处理 k=n,n−1,…,0k=n, n-1, \dots, 0,每层把 (nn−k)\binom{n}{n-k} 个单项式写出来再用 + 连上、套括号,最后量一遍长度。 小数据能跑通,n=3n=3 得到 4040,与题面样例一致。

瓶颈在哪? 展开式的单项式总个数是

∑k=0n(nk)=2n.\sum_{k=0}^{n}\binom{n}{k}=2^n .

nn 稍大就直接爆炸:n=30n=30 就是十亿量级的字符,而 nn 可以到 10910^9。 即使不真的拼接、只按 kk 做 O(n)O(n) 的线性求和,10910^9 次循环也远超 1 秒。 必须找到一个只依赖 nn 和 DD 的闭形式公式,而不是枚举任何一枚单项式。

第一步:把单项式自身的长度求和。 单个单项式 ai1ai2⋯aika_{i_1}a_{i_2}\cdots a_{i_k} 的长度 = kk 个字母 a + 这些下标的十进制位数之和。看所有含 kk 个 aa 的单项式(共 (nk)\binom{n}{k} 个):

  • 字母 a 的总贡献是 k(nk)k\binom{n}{k}。
  • 下标的贡献靠对称性:固定一个下标 ii,它在含 kk 个 aa 的单项式里出现当且仅当 另外 k−1k-1 个从剩下 n−1n-1 个里选,即出现 (n−1k−1)\binom{n-1}{k-1} 次。 所以下标总贡献是 d(i)(n−1k−1)d(i)\binom{n-1}{k-1},对 ii 求和得 D(n−1k−1)D\binom{n-1}{k-1}。

对所有 k=1..nk=1..n 求和:

∑k=1nk(nk)=n2n−1,∑k=1n(n−1k−1)=2n−1.\sum_{k=1}^{n} k\binom{n}{k}=n2^{n-1}, \qquad \sum_{k=1}^{n}\binom{n-1}{k-1}=2^{n-1}.

所以全部单项式自身的总长度是

Smono=2n−1(n+D).S_{\text{mono}}=2^{n-1}(n+D).

第二步:把结构字符逐个点清。 结构字符是 x、指数数字、括号、+:

结构成分 数量
各项之间的 +(n+1n+1 项之间有 nn 个) nn
最高次项的 x 11
中间项的 x(k=1..n−1k=1..n-1) n−1n-1
中间项的括号(每项一对) 2(n−1)2(n-1)
全部指数数字(d(1)+⋯+d(n)d(1)+\cdots+d(n),因为 k=n,1..n−1k=n,1..n-1 全覆盖) DD
各项内部连接单项式的 + 2n−n−12^n-n-1

最后一行值得单独验一下:第 kk 项内部有 (nn−k)=(nk)\binom{n}{n-k}=\binom{n}{k} 个单项式, 需要 (nk)−1\binom{n}{k}-1 个 +;对 k=1..n−1k=1..n-1 求和得

∑k=1n−1((nk)−1)=(2n−2)−(n−1)=2n−n−1.\sum_{k=1}^{n-1}\left(\binom{n}{k}-1\right) =\left(2^n-2\right)-(n-1)=2^n-n-1 .

指数那行的 DD 其实包含了 d(1)=1d(1)=1,而 k=1k=1 时不写指数,所以实际是 D−1D-1—— 这和“最高次项固定写 xnx^n、其余项写 xk (k≥2)x^k\ (k\ge 2)”是一致的,即指数数字总数为

d(n)+∑k=2n−1d(k)=D−1.d(n)+\sum_{k=2}^{n-1}d(k)=D-1 .

第三步:合并。 把上表相加:

t(n)=2n−1(n+D)+n+1+(n−1)+2(n−1)+(D−1)+(2n−n−1) t(n)=2^{n-1}(n+D)+n+1+(n-1)+2(n-1)+(D-1)+\left(2^n-n-1\right)

整理后所有多余项恰好抵消,得到极简的闭形式:

 t(n)=2n−1(n+D)+2n+3n+D−4 \boxed{\,t(n)=2^{n-1}(n+D)+2^n+3n+D-4\,}

DD 按十进制位数分段算:lenlen 位数的区间为 [10len−1, 10len−1][10^{len-1},\,10^{len}-1], 与 [1,n][1,n] 取交后整段长度乘以 lenlen 累加,最多循环 1010 次。全式只有 O(log⁡n)O(\log n) 的快速幂,n≤109n\le 10^9 时运算量在几十次以内。

小数据核对。 直接按定义展开和按公式计算完全吻合:

nn 展开式 tt
1 x+a1x+a_1 44
2 x2+x(a1+a2)+a1a2x^2+x(a_1+a_2)+a_1a_2 1616
3 x3+x2(a1+a2+a3)+x(a1a2+a1a3+a2a3)+a1a2a3x^3+x^2(a_1+a_2+a_3)+x(a_1a_2+a_1a_3+a_2a_3)+a_1a_2a_3 4040
4 x4+x3(⋅)+x2(⋅)+x(⋅)+a1a2a3a4x^4+x^3(\cdot)+x^2(\cdot)+x(\cdot)+a_1a_2a_3a_4 9292

n=3n=3 与题面样例的 4040 一致,因此“^ 不计长、x1x^1 简写为 xx”这条读法是被数据确认的。

代码

Python 版:

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 04:55
# update_at: 2026-10-08 04:55

import sys

MOD = 10000     # 题面要求对 10000 取余
MAX_DIGIT = 10  # n <= 10^9,位数不超过 10 位


def power_mod(base: int, exp: int, mod: int) -> int:
    """快速幂:返回 base 的 exp 次方对 mod 取余。"""
    result = 1
    base %= mod
    while exp:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result


def digit_length_sum(n: int) -> int:
    """返回 D mod 10000,其中 D 是 1..n 每个数的十进制位数之和。

    按位数分段:len 位数的区间是 [10^(len-1), 10^len - 1],与 1..n 求交后整段累加。
    """
    total = 0
    for length in range(1, MAX_DIGIT + 1):
        low = 10 ** (length - 1)          # 本段的起点
        if low > n:
            break                         # 后面更长的位数段一定也为空
        high = min(n, low * 10 - 1)       # 本段落在 1..n 内的终点
        total = (total + (high - low + 1) * length) % MOD
    return total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    # 展开式总长 t(n) = 2^(n-1)(n + D) + 2^n + 3n + D - 4
    digit_sum = digit_length_sum(n)
    answer = (
        power_mod(2, n - 1, MOD) * (n + digit_sum)                  # 2^(n-1) * (n + D)
        + power_mod(2, n, MOD)                                      # 2^n
        + 3 * n + digit_sum - 4                                     # 3n + D - 4
    ) % MOD
    print(answer)


if __name__ == "__main__":
    solve()

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 04:55
 * update_at: 2026-10-08 04:55
 */
// 一本通 1811《多项式相乘》
// 题意:展开 (x+a_1)(x+a_2)...(x+a_n),按题面写法统计展开式总长 t,输出 t mod 10000。
//   n=2: x^2+x(a_1+a_2)+a_1a_2        长度 16
//   n=3: x^3+x^2(a_1+a_2+a_3)+x(a_1a_2+a_1a_3+a_2a_3)+a_1a_2a_3  长度 40(题面样例)
// 计长规则:x/a/(/)/+ 各 1;指数的每个数字 1;下标的每个数字 1。'^' 不计长;
//   x^1 只写 x;常数项不写 x、不带括号。
//
// 记 d(i) 为 i 的十进制位数,D = sum_{i=1}^{n} d(i)。展开化简后总长满足闭形式:
//   t(n) = 2^{n-1} * (n + D) + 2^n + 3n + D - 4
// 于是只需快速幂求 2^{n-1}、2^n mod 10000,并按十进制位数分段求 D,整体 O(log n)。
#include <cstdio>

typedef long long ll;

const int MOD = 10000; // 题面要求对 10000 取余

// 快速幂:底数 b、指数 e,返回 b^e mod m
ll power_mod(ll b, ll e, ll m)
{
    ll result = 1 % m;
    b %= m;
    while (e > 0) {
        if (e & 1LL) {
            result = result * b % m;
        }
        b = b * b % m;
        e >>= 1;
    }
    return result;
}

// 按十进制位数分段统计 D = sum_{i=1}^{n} d(i) mod MOD
// 第 len 位数的区间是 [10^{len-1}, 10^len - 1],与 [1, n] 取交集后整段相加
ll digit_length_sum(ll n)
{
    ll sum_len = 0;
    ll low = 1;                                  // 当前位数段的起点
    for (int len = 1; len <= 18 && low <= n; len++) {
        ll high = low * 10 - 1;                  // 该位数段的终点(可能超过 n)
        if (high > n) {
            high = n;
        }
        ll cnt = high - low + 1;                 // 这一段落在 [1, n] 内的整数个数
        sum_len = (sum_len + cnt % MOD * len) % MOD;
        low = high + 1;
    }
    return sum_len;
}

int main()
{
    ll n;
    if (scanf("%lld", &n) != 1) {
        return 0;
    }

    ll digit_sum = digit_length_sum(n);          // D mod MOD
    ll n_mod = n % MOD;
    ll p_half = power_mod(2, n - 1, MOD);        // 2^{n-1} mod MOD(n >= 1,指数非负)
    ll p_full = power_mod(2, n, MOD);            // 2^n mod MOD

    // t(n) = 2^{n-1}(n + D) + 2^n + 3n + D - 4,逐项在模 10000 下累加
    ll answer = p_half * ((n_mod + digit_sum) % MOD) % MOD;
    answer = (answer + p_full) % MOD;
    answer = (answer + 3 * n_mod) % MOD;
    answer = (answer + digit_sum) % MOD;
    answer = (answer - 4 + MOD) % MOD;           // 结尾的 -4,加 MOD 防负数

    printf("%lld\n", answer);
    return 0;
}

复杂度

  • 时间:按位数分段求 DD 循环 O(log⁡10n)O(\log_{10} n) 次;快速幂两次 O(log⁡n)O(\log n)。 总体 O(log⁡n)O(\log n),n≤109n\le 10^9 时不到 100100 次基本运算,实测 0 ms 量级(限时 1000 ms)。
  • 空间:只用常数个整型变量,O(1)O(1)(限时 128 MB)。
  • 与 C++ 解法的关系:main.cpp 与 main.py 是同一公式的两种落地, 连“负数取模加 1000010000”的处理都一致;Python 版只用标准库,不存在 TLE/MLE 风险。

总结

  • 字符串计数先拆成“组件贡献”:把总长拆成“所有单项式自身”+“结构字符”两块, 每块都只与 nn、DD 有关,指数级的展开式一下变成两三个代数项。
  • 对称性是组合计数的标准武器:固定一个下标 ii,它在含 kk 个 aa 的单项式里 出现 (n−1k−1)\binom{n-1}{k-1} 次;换成对 kk 求和就是 2n−12^{n-1}, 于是“下标位数之和”从 2n2^n 项规模降到 D⋅2n−1D\cdot 2^{n-1}。
  • 别忘了逐个点清结构字符:+、括号、x、指数这些零碎项极易漏一个 (尤其“括号内部 + 的总数是 2n−n−12^n-n-1”和“指数数字总数是 D−1D-1”), 代价是一次数值验证:n=3n=3 必须得到 4040。
  • 答案取模不影响推导:公式里所有中间量都能在模 1000010000 下计算, 只要注意末尾的 -4 要加回模数避免负数。
  • 数据来源提示:本题素材源带有数据生成脚本(data.py), data/ 的 10 组点是自造的(覆盖 n=1,2,3,9,10,100,10000,123456789,999999999,109n=1,2,3,9,10,100,10000,123456789,999999999,10^9), 题面为网络重建版本,出题意图与官方原题可能存在偏差;本解法的正确性以 与题面定义逐字核对的小数据(n=1,2,3,4n=1,2,3,4)和真实数据全部通过为准。