古老的打字机 > 43499582 尝试的题解

长度相同的字符串拥有相同的出现次数
dp[a][b]记录了在敲击a次时长度为b的字符串出现次数

由于概率平均 每一个字符串出现占其中的

每一个长度为b的字符串又拥有b-i+1个长度为i的子串
于是敲击a次长度为i的某一个子串的出现次数为

#include <bits/stdc++.h>
using namespace std;
long long dp[10000][10000]={0};
long long cans[10000]={0};
const long long mod=1e9+7;
long long gcd(long long a,long long b,long long &x,long long &y)
{
    if (b)
    {
        long long c=gcd(b,a%b,x,y);
        long long t=x;
        x=y;
        y=t-a/b*y;
        return c;      
    }
    else
    {
        x=1,y=0;
        return a;
    }
}
long long inv(long long a)
{
    long long x,y,d=gcd(a,mod,x,y);
    if(d==1)
        if(x%mod<=0)return x%mod+mod;
        else return x%mod;
    else return -1;
}
long long qpow(long long a,long long b) {long long res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int main()
{
    long long l,q;
    cin>>q>>l;
    dp[0][0]=1;
    dp[0][1]=0;
    for (long long i=1;i<=l;i++)
    {
        dp[i][0]=(dp[i-1][0]+dp[i-1][1])%mod;
        for(long long j=1;j<i;j++) dp[i][j]=(dp[i-1][j-1]*26+dp[i-1][j+1])%mod;
        dp[i][i]=(dp[i-1][i-1]*26)%mod;
    }
    for (long long i=1;i<=l;i++)
        for(long long j=i;j<=l;j++)
            cans[i]=(cans[i]+dp[l][j]*(j-i+1)%mod*inv(qpow(26,i))%mod)%mod;
    long long ans=0;
    while(q--)
    {
        string s;long long score;
        cin>>s>>score;
        ans=(ans+cans[s.size()]*score%mod)%mod;
    }
    cout<<(ans+mod)%mod<<endl;
    return 0;
}