1.题目描述：点击打开链接
2.解题思路：本题是一道组合数学题，一开始用递归的思想做，但结果错误。学习了别人的解法后，豁然开朗。正确的解法是关注每一位数对整体的贡献值。比如输入的n位数是D1D2D3…D(n-1)D(n)，那么当D(i)作为个位数时，它的前面必然有一个‘+’。剩下的k-1个‘+’被安置在剩下的n-2个空隙中，因此一共有C(n-2,k-1)种情况，D(i)的总贡献值是D(i)*C(n-2,k-1)；同理，当D(i)作为十位数时，D(i+1)必然是个位数，D(i+1)前面必然有一个‘+’，那么剩下的k-1个‘+’被安置在剩下的n-3个空隙中，因此有C(n-3,k-1)种情况，D(i)的总贡献值是D(i)*10*C(n-3,k-1)，以此类推。这样的D(i)最多只能是在第n-k位（个位算第1位，十位算第2位，依次类推），这样便计算出了第一部分贡献值。
第二部分的贡献值来自‘+’后面的那位数。假设D(i+1)前有一个‘+’且它恰好是第n位时，必然是k个‘+’被安置在它前面的n-1个空隙中，因此有C(n-1,k)种情况，，那么D(i+1)的总贡献值是D(i+1)*C(n-1,k)；若D(i+1)前有一个‘+’且它恰好是第n-1位，那么总贡献是D(i+1)*10*C(n-2,k)，以此类推。最后，将两部分之和相加就是最终的答案。
由于涉及组合数取模，前缀和。因此应该事先在初始化中计算出这些数的值，便于后续处理。根据组合数公式：C(n,k)=n!/k!/(n-k)!，因此应当事先计算出n!(mod M)的值。由于本题中M是一个素数，可以考虑用逆元来代替除法。根据费马小定理易知：n^(M-1)≡1(mod M)，即n*n^(M-2))≡1(mod M)。因此n的逆元是n^(M-2)。这是本题第一个新知识点。计算出了n!的逆元之后，再根据n!=n*(n-1)!，两边同时乘以INV(n),INV(n-1)，化简得：INV(n-1)=n*INV(n)，因此可以利用该公式递推求出其他的逆元，这是本题的第二个新知识点。本题通过考虑每一位数贡献值的角度则是第三个新知识点。
注意：输出long long型时推荐用%I64d输出。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;typedef long long LL;const int MOD = 1000000000 + 7;const int N = 110000;int n, k, a[N],sum[N];char st[N];LL fac[N], inv[N];LL pow_mod(LL a, LL k){LL ans = 1;while (k > 0){if (k & 1)ans = ans*a%MOD;a = a*a%MOD;k >>= 1;}return ans;}void init()//计算阶乘取模，逆元{fac[0] = 1;for (int i = 1; i <= n; i++)fac[i] = fac[i – 1] * i%MOD;inv[n] = pow_mod(fac[n], MOD – 2);for (int i = n – 1; i >= 0; i–)inv[i] = inv[i + 1] * (i + 1) % MOD;}int C(int n, int k)//计算组合数取模{return fac[n] * inv[k] % MOD*inv[n – k] % MOD;}int main(){//freopen("t.txt", "r", stdin);scanf("%d%d", &n, &k);scanf("%s", st + 1);sum[0] = 0;for (int i = 1; i <= n; i++){a[i] = st[i] – '0';sum[i] = sum[i – 1] + a[i];}init();LL ans = 0;LL s;LL base = 1;//base一定要设为LL！for (int i = 1; i <= n – k; i++){s = (LL)sum[n – i] * base%MOD;//第一部分的贡献ans += (LL)s*C(n – i – 1, k – 1) % MOD;s = (LL)a[n – i + 1] * base%MOD;//第二部分的贡献ans += s*C(n – i, k) % MOD;base *= 10;ans %= MOD;base %= MOD;}printf("%I64d\n", ans);return 0;}
此刻睡觉的口水将变成明天流下的泪水。
