Codeforces Round #295 (Div. 1) C. Pluses everywhere (組合數(shù)學(xué)+乘法逆元)
來源：程序員人生 發(fā)布時間：2015-03-31 08:36:44 閱讀次數(shù)：3586次
這題可以這樣想：
對當前第i位來講，該位若在個位上出現(xiàn)，那末第i位和第i+1位中間肯定有1個“+”，剩下的k⑴個“+”散布在剩下的n⑵個空隙中，所以出現(xiàn)的總次數(shù)是C（n⑵,k)。同理，在10位上出現(xiàn)的總次數(shù)是C(n⑶,k)。因而每一個數(shù)字的貢獻值就能夠求出來了，累加便可。
所以大體思路是遍歷所有可能出現(xiàn)的位數(shù)，從個位開始，分成兩部份計算，1部份用前綴和計算出前面所有的在該位上的貢獻和，另外一部份算出當前位置在該位上的貢獻值。
然后對求組合數(shù)，可以先將階乘預(yù)處理出來，然后用乘法逆元求出組合數(shù)的值。
代碼以下：
#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(⑴.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e⑼;
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⑴]*i;
if(fac[i]>=mod) fac[i]%=mod;
}
inv_fac[n]=qsm(fac[n],mod⑵);
for(i=n⑴;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⑴];
}
for(i=1;i<=n-k;i++){
s=(LL)sum[n-i]*base%mod;
ans+=s*comb(n-i⑴,k⑴)%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
",ans);
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
