CodeForces - 520E Pluses everywhere

畿王 · 2018-09-22 15:31:58 · 个人记录

题意

给出一个长度为n的字符串，给出一个整数k，现在要在这字符串中加k个'+'号，变成一个合法的表达式，求所有表达式的和为多少。

思路

枚举固然不行，dp算每个式子的复杂度也不够，所以换个方向考虑，计算每一位的贡献，也就是这个数字做个位，十位，百位……的情况总和，假设这个数为A，则有A+,AX+,AXX+,……这些数，考虑加号的摆放方案，n个数共有n-1个空，A+占了1个空，还剩n-1-1个空来放剩下的k-1个加号，这就成了一个组合数问题。同理，AX+则是剩下n-1-2个空来放k-1个的加号，另外注意加号不能放在最后，所有只需处理前缀和，算合法的即可。

另外，还需注意的细节就是最后被加号分割的数其实并没有算上贡献，对于倒数第i个数，还剩n-i个空来放k个加号，在乘上10^i即可。

代码

#include<bits/stdc++.h>
#define M 100005
#define LL long long
using namespace std;
const LL mod=1e9+7;
int n,k;
char s[M];
LL jie[M],inv[M],dp[1000][1000];
int A[M],sum[M];
LL Pow(LL x){
    int r=mod-2;
    LL res=1;
    while(r){
        if(r&1)res=res*x%mod;
        x=x*x%mod;
        r>>=1;
    }
    return res;
}
void Init(){//预处理阶乘以及其逆元
    jie[0]=inv[0]=1;
    for(int i=1;i<M;i++){
        jie[i]=jie[i-1]*i%mod;
        inv[i]=Pow(jie[i]);
    }
}
LL C(int a,int b){//算组合数C(a,b)
    return jie[a]*inv[b]%mod*inv[a-b]%mod;
}
int main(){
    Init();
    scanf("%d %d %s",&n,&k,s+1);
    for(int i=1;i<=n;i++){
        A[i]=s[i]-'0';
        sum[i]=sum[i-1]+A[i];
    }
    LL pow10=1,ans=0;
    for(int i=1;i<=n-k;i++){
        ans=(ans+1LL*sum[n-i]*pow10%mod*C(n-i-1,k-1)%mod)%mod;
        ans=(ans+1LL*A[n-i+1]*pow10%mod*C(n-i  ,k  )%mod)%mod;
        pow10=(pow10*10)%mod;
    }
    cout<<ans<<endl;
    return 0;
}