I 古老的打字机题解

$description:$

你有一个字符串 $S.$ 一开始它是空串 $.$

你会随机 $m$ 次 $,$ 每次你会输入一个小写字母或按下 $Backspace.$

有 $n$ 个字符串 $T_i,$ 第 $i$ 个字符串的权值为 $v_i$

对于所有生成的字符串 $,$ 求出给出的 $n$ 个串的 $\sum$ $($ 出现次数 $\times$ 权值 $)$ 之和 $.$

$solution:$

对 $n$ 个串建出 $AC$ 自动机 $.$

记有效字符为没有被 $Backspace$ 退格掉的字符 $.$

记 $dp[i][j]$ 为用了 $i$ 个字符之后走到节点 $j$ 的方案数 $.$

记 $f[i][j]$ 为打了 $i$ 次字 $,$ 一共打出来 $j$ 个有效字符的方案数 $.$

$dp$ 出上述两个数组之后直接计算答案即可 $.$

复杂度 $O(nm*26)$

$code:$

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int P = 1e9 + 7,N = 2050,M = 2050;
inline void upd(int &x,int y){ x = (x+y>=P)?(x+y-P):(x+y); }
int ans,nxt[N][26],val[N],n,m;
struct Trie{
    int rt,cnto;
    inline void init(){ rt = 0,cnto = 0; }
    int ch[N][26],fail[N];
    inline void Ins(char *s,int l,int v){
        int now = rt,i,c;
        for (i = 0; i < l; ++i){
            c = s[i] - 'a';
            if (!ch[now][c]) ch[now][c] = ++cnto;
            now = ch[now][c];
        }
        upd(val[now],v);
    }
    inline void build(){
        int i,j,x;
        n = cnto;
        queue<int>Q; while (!Q.empty()) Q.pop();
        fail[0] = 0;
        for (i = 0; i < 26; ++i)
            if (ch[0][i]) fail[ch[0][i]] = 0,Q.push(ch[0][i]); else ch[0][i] = 0;
        while (!Q.empty()){
            x = Q.front(),Q.pop(); upd(val[x],val[fail[x]]);
            for (i = 0; i < 26; ++i)
                if (ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i],Q.push(ch[x][i]);
                else ch[x][i] = ch[fail[x]][i];
        }
        for (i = 0; i <= n; ++i)
        for (j = 0; j < 26; ++j) nxt[i][j] = ch[i][j];
    }
}T;
string SS; char s[N];
int k1[N],pw[N];
inline void DP1(){
    static int f[N],g[N],i,t; memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
    f[0] = 1;
    for (t = 1; t <= m; ++t){
        for (i = 0; i <= m; ++i) g[i] = f[i],f[i] = 0;
        for (i = 0; i <= m; ++i) if (g[i]){
            upd(f[i+1],g[i]);
            upd(f[i-(i?1:0)],1ll*g[i]*pw[i?1:0]%P);
        }
    }
    for (i = 0; i <= m; ++i) upd(k1[i],f[i]);
}
int f[N],g[N];
inline void DP2(){
    int i,j,v;
    for (i = 0; i <= n; ++i) g[i] = f[i],f[i] = 0;
    for (i = 0; i <= n; ++i) if (v=g[i])
    for (j = 0; j < 26; ++j) upd(f[nxt[i][j]],v);
}
int main(){
    int i,j,ret,sum;
    T.init();
    cin >> n >> m;
    for (i = 1; i <= n; ++i){
        cin >> SS;
        for (j = 0; j < SS.size(); ++j) s[j] = SS[j];
        cin >> j;
        T.Ins(s,(int)SS.size(),j);
    }
    T.build();pw[0] = 1;
    for (i = 1; i <= 2000; ++i) pw[i] = pw[i-1] * 26ll % P;
    DP1();
    f[0] = 1;

    for (i = 1; i <= m; ++i){
        DP2();
        ret = 0;
        for (j = i; j <= m; ++j) ret = (ret + (LL)pw[j-i] * k1[j]) % P;
        sum = 0;
        for (j = 0; j <= n; ++j) upd(sum,(LL)f[j] * val[j] % P);
        ans = (ans + 1ll *ret * sum) % P;
    }
    cout << ans << '\n';
    return 0;
}

I 古老的打字机 题解

I 古老的打字机题解