题解：P9613 [CERC2019] K==S

· · 题解

abc 出原题蚌埠住了。

多模匹配于是建 ACAM，然后把树边和 fail 树边看成转移边，于是可以 dp。

不能完整匹配所以在结束处打标记，把有标记的节点的转移边全部扔掉即可。记得要下传标记。

然后这个 dp 显然是可以变成转移矩阵的，于是把转移矩阵构造出来，跑一遍矩阵快速幂即可。

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
#define N 105
int tp;
int tr[N+5][35];
int tre[N+5];
int fail[N+5];
void ins(string s){
    int flc=0;
    for(int i=0;i<s.size();i++){
        int nxt=s[i]-'a';
        if(!tr[flc][nxt])
        tr[flc][nxt]=++tp;
        flc=tr[flc][nxt];
    }
    tre[flc]=1;
}
void fail_(){
    queue<int>q;
    for(int i=0;i<26;i++)
    if(tr[0][i])q.push(tr[0][i]);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        if(tr[x][i]){
            fail[tr[x][i]]=tr[fail[x]][i];
            tre[tr[x][i]]|=tre[fail[tr[x][i]]];
            q.push(tr[x][i]);
        }else tr[x][i]=tr[fail[x]][i];
    }
}
int a[105][105];
int b[105][105];
int ret[105][105];
void zc(){
    memset(b,0,sizeof b);
    for(int i=0;i<=tp;i++)
    for(int j=0;j<=tp;j++)
    for(int k=0;k<=tp;k++)
    b[i][k]=(b[i][k]+a[i][j]*a[j][k]%mod)%mod;
    for(int i=0;i<=tp;i++)
    for(int j=0;j<=tp;j++)
    a[i][j]=b[i][j];
}
void c(){
    memset(b,0,sizeof b);
    for(int i=0;i<=tp;i++)
    for(int j=0;j<=tp;j++)
    for(int k=0;k<=tp;k++)
    b[i][k]=(b[i][k]+ret[i][j]*a[j][k]%mod)%mod;
    for(int i=0;i<=tp;i++)
    for(int j=0;j<=tp;j++)
    ret[i][j]=b[i][j];
}
signed main(){
    int n,k;
    cin>>n>>k;
    while(k--){
        int x;
        cin>>x;
        string flc;
        cin>>flc;
        ins(flc);
    }
    fail_();
    for(int i=0;i<=tp;i++)
    for(int j=0;j<26;j++)
    if(!tre[i]&&!tre[tr[i][j]])
    ret[i][tr[i][j]]++,
    a[i][tr[i][j]]++;
    n--;
    while(n){
        if(n&1)
        c();
        n>>=1;
        zc();
    }
    int flc=0;
    for(int i=0;i<=tp;i++)
    flc=(flc+ret[0][i])%mod;
    cout<<flc;
    return 0;
}
//「那个她最喜欢的，陪伴在她身边的，身为她未婚夫的温柔大哥哥已经不存在了。
// 如今沾染了些污秽的我，到底有什么脸去见她？」

//「是吗……这样啊。」
// 她感觉很落寞。
//「你们确实都会这么说呢。」