首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#13120

数字之和 题目描述 给定一个数字字符串 n,定义一次操作为:移除字符串中一个非空子串,并将剩余部分拼接形成新数字。 求所有可能操作方案生成的新数字之和,结果对…

数字之和

题目描述

给定一个数字字符串 n,定义一次操作为:移除字符串中一个非空子串,并将剩余部分拼接形成新数字。

求所有可能操作方案生成的新数字之和,结果对 109+7取模。

输入格式

一行字符串 n

输出格式

一个整数,表示所有方案生成数字之和取模后的结果。


输入样例#1

1003

输出样例#1

339

输入样例#2

123

输出样例#2

52

说明提示

【数据范围】

1≤∣n∣≤105,| n |表示字符串长度。

限制

时间限制:1000ms

内存限制:256MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; 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 &gt; 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 &lt;= 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 &gt;&gt; n;     int L = n.size();     precompute(L);          long long ans = 0;     for (int k = 0; k &lt; L; ++k) {         int d = n[k] - '0';         if (d == 0) {             continue; // 贡献为0,可直接跳过         }                  // 计算左侧贡献         long long left = 0;         if (k &gt; 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 &gt; 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 &lt;&lt; ans &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。