本文共 1295 字，大约阅读时间需要 4 分钟。
ps:可能组合数一不小心打错了，请发现的大佬提出，谢谢。
我们来讨论每一位数$a_{i}$被算了多少次。总共有$n-1$个空位可以放$'+'$所以，$a_{i}$左边有$i-1$个空位，右边$n-1-(i-1)$个。举个例子来说~~（手动模拟一下）~~，如果数$a_{i}$右边有一个加号，则剩下$n-2$个空位放$k-1$个加号的方案里，每种方案$a_{i}$都当做各位记录到答案里，所以对答案影响：$C^{k-1}_{n-2}*$ $a_{i}$。假设右边第一个不放，第二个放加号，则还有$n-3$个空位，$k-2$个加号。（因为$a_{i}$右边的以为不能放加号）对答案影响： $C_{n-3}^{k-2}*10*$ $a_{i}$。$emm……$规律好像找出来了。这样一直递推下去~~（找规律）~~的话。到$a_{n-1}$ 和 $a_{n}$ 位填的话。对答案的影响： $C^{1}_{n-k-2}*10^{k-1}*a_{i}$ 但是，我们发现，最后一位数的后面好像并不能放加号。也就是说，最后一位需要特判。。。所以，当右边全空着的时候对答案的贡献 $10^{i}*C_{n-i-1}^{i}*a_{i}$全部统计起来，输出就好。代码奉上。#include#include #include using namespace std;const long long p=1e9+7;int n,k;long long ans[100010];char a[100010];long long pen[100010];//阶乘long long rpen[100010];//阶乘逆元long long num[100010];//系数long long pow2(long long a,long long b){ long long res=1; for(;b;b>>=1,a=a*a%p) if(b&1) res=res*a%p; return res%p;}void rebiut(){ num[0]=pen[0]=rpen[0]=1; for(int i=1;i<=n;i++) pen[i]=pen[i-1]*i%p, rpen[i]=pow2(pen[i],p-2), num[i]=10*num[i-1]%p; return ;}long long C(long long n,long long k)//计算组合数，n下面，k上面{ if(k<0||k>n||n<0) return 0; else return ((pen[n]*rpen[k])%p)*rpen[n-k]%p;}long long now;int main(){ scanf("%d%d",&n,&k); scanf("%s",a); rebiut(); for(int i=0;i
转载地址：http://xdrfa.baihongyu.com/