本文主要是介绍Codeforces Round #295 (Div. 1) C. Pluses everywhere (组合数学+乘法逆元)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题可以这样想：
对于当前第i位来说，该位若在个位上出现，那么第i位和第i+1位中间肯定有一个“+”，剩下的k-1个“+”分布在剩下的n-2个空隙中，所以出现的总次数是C（n-2,k)。同理，在十位上出现的总次数是C(n-3,k)。于是每个数字的贡献值就可以求出来了，累加即可。
所以大体思路是遍历所有可能出现的位数，从个位开始，分成两部分计算，一部分用前缀和计算出前面所有的在该位上的贡献和，另一部分算出当前位置在该位上的贡献值。
然后对于求组合数，可以先将阶乘预处理出来，然后用乘法逆元求出组合数的值。
代码如下：
#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#define LL long long
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
char st[110000];
int n, k, a[110000], sum[110000];
LL fac[110000], inv_fac[110000];
LL qsm(LL n, LL k)
{LL ans=1;while(k>0){if(k&1)ans=ans*n%mod;k>>=1;n=n*n%mod;}return ans;
}
void init()
{int i;fac[0]=1;for(i=1;i<=n;i++){fac[i]=fac[i-1]*i;if(fac[i]>=mod) fac[i]%=mod;}inv_fac[n]=qsm(fac[n],mod-2);for(i=n-1;i>=0;i--){inv_fac[i]=inv_fac[i+1]*(i+1);if(inv_fac[i]>=mod) inv_fac[i]%=mod;}
}
LL comb(LL n, LL k)
{return fac[n]*inv_fac[k]%mod*inv_fac[n-k]%mod;
}
int main()
{int i;LL ans=0, base=1, s;scanf("%d%d",&n,&k);scanf("%s",st+1);init();sum[0]=0;for(i=1;i<=n;i++){a[i]=st[i]-'0';sum[i]=a[i]+sum[i-1];}for(i=1;i<=n-k;i++){s=(LL)sum[n-i]*base%mod;ans+=s*comb(n-i-1,k-1)%mod;s=(LL)a[n-i+1]*base%mod;ans+=s*comb(n-i,k)%mod;base=base*10;if(ans>=mod) ans%=mod;if(base>=mod) base%=mod;}printf("%I64d\n",ans);return 0;
}
这篇关于Codeforces Round #295 (Div. 1) C. Pluses everywhere (组合数学+乘法逆元)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
