把展开式的字符拆成单项式与结构两部分,用对称性把前者求和成 2^(n-1)(n+D),化简得闭形式 O(log n) 求解。
OJ: roj
题目 ID: 1811
难度:普及+/提高-
标签:数学组合数学快速幂python
创建: 2026-10-08 04:55
更新: 2026-10-08 04:55
形式化题目
给定正整数
按题面规定的写法完整展开成一行文本,统计这行文本的总字符数
题面规定的写法(以
即按
(最高次):只写 ,省略系数 、不带括号; 时写作 。 (中间项):写作 后面紧跟一对括号, 括号里是 个“ 个 相乘”的单项式,用 +连接;时指数 不写。 (常数项):只有 一个单项式,不写 、不带括号。
计长规则:x、a、(、)、+ 每个计 ^ 不在题面枚举的计数字符里,不计长度。
于是答案依赖两个量:
(
正解
思路
朴素做法。 按定义逐项拼接字符串,依次处理 + 连上、套括号,最后量一遍长度。
小数据能跑通,
瓶颈在哪? 展开式的单项式总个数是
第一步:把单项式自身的长度求和。 单个单项式 a + 这些下标的十进制位数之和。看所有含
- 字母
a的总贡献是。 - 下标的贡献靠对称性:固定一个下标
,它在含 个 的单项式里出现当且仅当 另外 个从剩下 个里选,即出现 次。 所以下标总贡献是 ,对 求和得 。
对所有
所以全部单项式自身的总长度是
第二步:把结构字符逐个点清。 结构字符是 x、指数数字、括号、+:
| 结构成分 | 数量 |
|---|---|
各项之间的 +( |
|
最高次项的 x |
|
中间项的 x( |
|
| 中间项的括号(每项一对) | |
| 全部指数数字( |
|
各项内部连接单项式的 + |
最后一行值得单独验一下:第 +;对
指数那行的
第三步:合并。 把上表相加:
整理后所有多余项恰好抵消,得到极简的闭形式:
小数据核对。 直接按定义展开和按公式计算完全吻合:
| 展开式 | ||
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 |
^ 不计长、
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:按位数分段求
循环 次;快速幂两次 。 总体 , 时不到 次基本运算,实测 0 ms 量级(限时 1000 ms)。 - 空间:只用常数个整型变量,
(限时 128 MB)。 - 与 C++ 解法的关系:
main.cpp与main.py是同一公式的两种落地, 连“负数取模加”的处理都一致;Python 版只用标准库,不存在 TLE/MLE 风险。
总结
- 字符串计数先拆成“组件贡献”:把总长拆成“所有单项式自身”+“结构字符”两块,
每块都只与
、 有关,指数级的展开式一下变成两三个代数项。 - 对称性是组合计数的标准武器:固定一个下标
,它在含 个 的单项式里 出现 次;换成对 求和就是 , 于是“下标位数之和”从 项规模降到 。 - 别忘了逐个点清结构字符:
+、括号、x、指数这些零碎项极易漏一个 (尤其“括号内部+的总数是”和“指数数字总数是 ”), 代价是一次数值验证: 必须得到 。 - 答案取模不影响推导:公式里所有中间量都能在模
下计算, 只要注意末尾的 -4要加回模数避免负数。 - 数据来源提示:本题素材源带有数据生成脚本(
data.py),data/的 10 组点是自造的(覆盖), 题面为网络重建版本,出题意图与官方原题可能存在偏差;本解法的正确性以 与题面定义逐字核对的小数据( )和真实数据全部通过为准。