国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > Codeforces Round #295 (Div. 1) C. Pluses everywhere (组合数学+乘法逆元)

Codeforces Round #295 (Div. 1) C. Pluses everywhere (组合数学+乘法逆元)

来源:程序员人生   发布时间:2015-03-31 08:36:44 阅读次数:3381次

这题可以这样想:

      对当前第i位来讲,该位若在个位上出现,那末第i位和第i+1位中间肯定有1个“+”,剩下的k⑴个“+”散布在剩下的n⑵个空隙中,所以出现的总次数是C(n⑵,k)。同理,在10位上出现的总次数是C(n⑶,k)。因而每一个数字的贡献值就能够求出来了,累加便可。

      所以大体思路是遍历所有可能出现的位数,从个位开始,分成两部份计算,1部份用前缀和计算出前面所有的在该位上的贡献和,另外一部份算出当前位置在该位上的贡献值。

     然后对求组合数,可以先将阶乘预处理出来,然后用乘法逆元求出组合数的值。

代码以下:

#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; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生