Nowcodercontest5278I 古老的打字机(dp)

cnblogs界面

分析：对于每个字符串算权值，每个字符串贡献的次数只与当前串的长度和打字打出串的总长度有关

1.计算打出了 $i$ 数的方案数

$dp[i][j]$ 表示当前考虑i次，有j个字符打出来的方案数

$dp[i][j]\rightarrow dp[i+1][max(j-1,0)],dp[i][j]\cdot 26+dp[i+1][j+1]$

2.对于每种长度 $i$ ，枚举每个字符串的权值，固定从 $k$ 开始长度为 $|s_j|$ 的字符，其他字符随便，对于固定的字符除去 $26^{|s_i|}$ ，乘上开始位置 $k$ 的个数就能得到方案数

const int N=1e3+10,P=1e9+7;

int n,m;
char s[N][N];
int len[N],a[N];
ll Pow[N],C[N][N],IPow[N];
ll qpow(ll x,ll k) {
    ll res=1;
    for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
    return res;
}

int main(){
    Pow[0]=IPow[0]=1;
    rep(i,1,N-1) Pow[i]=Pow[i-1]*26%P;
    IPow[1]=qpow(26,P-2);
    rep(i,1,N-1) IPow[i]=IPow[i-1]*IPow[1]%P;
    n=rd(),m=rd();
    C[0][0]=1;
    rep(i,0,m-1) {
        rep(j,0,i) {
            (C[i+1][j+1]+=C[i][j]*26)%=P;
            (C[i+1][max(j-1,0)]+=C[i][j])%=P;
        }
    }
    rep(i,1,n) scanf("%s",s[i]+1),len[i]=strlen(s[i]+1),a[i]=rd();
    ll ans=0;
    rep(i,1,m) {
        ll s=0;
        rep(j,1,n) if(i>=len[j]) s=(s+1ll*(i-len[j]+1)*a[j]%P*IPow[len[j]])%P; // 权值贡献次数
        ans=(ans+s*C[m][i])%P;//长度为i的所有次数
    }
    printf("%lld\n",ans);
}