Codeforces Round #295 (Div. 1) C. Pluses everywhere (组合数学+乘法逆元) - c++编程基础

这题可以这样想：

对于当前第i位来说，该位若在个位上出现，那么第i位和第i+1位中间肯定有一个“+”，剩下的k-1个“+”分布在剩下的n-2个空隙中，所以出现的总次数是C（n-2,k)。同理，在十位上出现的总次数是C(n-3,k)。于是每个数字的贡献值就可以求出来了，累加即可。

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

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

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include
         #include 
         
           #include 
          
            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]; }www.2cto.com 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 ,ans); return 0; }