题解：AT_abc305_g [ABC305G] Banned Substrings

· · 题解

abc 出原题蚌埠住了。

强化问题为给定若干个串，求长度为 n 且不存在以给定串为子串的字符串数量。

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

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

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

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
#define N 1505
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<2;i++)
    if(tr[0][i])q.push(tr[0][i]);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=0;i<2;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[N][N];
int b[N][N];
int ret[N][N];
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--){
        string flc;
        cin>>flc;
        ins(flc);
    }
    fail_();
    for(int i=0;i<=tp;i++)
    for(int j=0;j<2;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;
}
//「为什么妮戈兰会被当作犯人啊？不管怎么想都很奇怪吧，与其说那家伙会做绑架这么麻烦的事情，不如说她肯定当场就把人烧一烧吃掉了。」

// 不，这也很难说啊。
// 缇亚忒虽然心中这么想，但并没说出口。