A22621. 数字之和
填空题
困难
知识点
题目描述
数字之和
题目描述
给定一个数字字符串 n，定义一次操作为：移除字符串中一个非空子串，并将剩余部分拼接形成新数字。
求所有可能操作方案生成的新数字之和，结果对 109+7 取模。
输入格式
一行字符串 n
输出格式
一个整数，表示所有方案生成数字之和取模后的结果。
输入样例#1
1003输出样例#1
339输入样例#2
123输出样例#2
52说明提示
1≤∣n∣≤105,| n |表示字符串长度。
参考答案
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAX_LEN = 1e5 + 10;
long long pow10[MAX_LEN];
long long inv9, inv81;
long long mod_pow(long long base, long long exp, int mod) {
long long result = 1;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return result;
}
void precompute(int L) {
pow10[0] = 1;
for (int i = 1; i <= L; ++i) {
pow10[i] = (pow10[i - 1] * 10) % MOD;
}
inv9 = mod_pow(9, MOD - 2, MOD);
inv81 = mod_pow(81, MOD - 2, MOD);
}
int main() {
string n;
cin >> n;
int L = n.size();
precompute(L);
long long ans = 0;
for (int k = 0; k < L; ++k) {
int d = n[k] - '0';
if (d == 0) {
continue; // 贡献为0，可直接跳过
}
// 计算左侧贡献
long long left = 0;
if (k > 0) {
long long count = (1LL * k * (k + 1)) / 2 % MOD;
int exponent = L - k - 1;
long long pow_val = pow10[exponent];
left = (count * pow_val) % MOD;
}
// 计算右侧贡献
long long right = 0;
int exponent = L - k - 1;
if (exponent > 0) {
long long part1 = (1LL * (L - k - 1) * pow10[exponent]) % MOD;
long long term1 = (part1 * inv9) % MOD;
long long part2 = (pow10[exponent] - 1 + MOD) % MOD;
long long term2 = (part2 * inv81) % MOD;
right = (term1 - term2 + MOD) % MOD;
}
long long total = (left + right) % MOD;
ans = (ans + 1LL * d * total) % MOD;
}
cout << ans << endl;
return 0;
}
上一题
下一题