题解：P9613 [CERC2019] K==S

· · 题解

前言

匹配。

Solution

多模匹配，考虑把 ACAM 搞出来。

然后你发现 n 非常大但是模式串总长只有 100，所以考虑 DP 然后用矩阵快速幂加速状物。

具体的转移就是设 f_{i,j} 表示考虑长度为 i 的字符串，当前在 ACAM 的 j 号节点，且未出现 ACAM 中的任意一个模式串的总方案数。

转移你就考虑往当前状态后面加一个字符，考虑转移后的节点是否有结束标记来决定这个转移是否发生。你发现这个转移是线性变换，套上一层矩阵快速幂就好了。

然后你发现你做完了。

Code

:::success[代码]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;

static const unsigned long long mod=1e9+7;
struct modint{
    // ...
};

class matrix{
    // ...
};

struct node{
    int ch[26];
    int fail;
    bool v;
    bool hasfind;
}t[110];
int nodecnt;
int newnode(){return ++nodecnt;}

void insert(string s){
    int p=0;
    for(char c:s){
        if(!t[p].ch[c-'a']) t[p].ch[c-'a']=newnode();
        p=t[p].ch[c-'a'];
    }
    t[p].v=true;
}

void build(){
    queue<int> q;
    for(int i=0;i<26;i++) if(t[0].ch[i]) q.push(t[0].ch[i]);
    while(!q.empty()){
        int p=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(t[p].ch[i]){
                t[t[p].ch[i]].fail=t[t[p].fail].ch[i];
                q.push(t[p].ch[i]);
            }else t[p].ch[i]=t[t[p].fail].ch[i];
        }
    }
}

bool find(int x){
    if(t[x].hasfind) return t[x].v;
    return t[x].hasfind=true,t[x].v|=find(t[x].fail);
}

int n,k;

int main(){
    cin.tie(0)->sync_with_stdio(false);

    cin>>n>>k;
    for(int i=1,len;i<=k;i++){
        string s;cin>>len>>s;
        insert(s);
    }build();

    matrix v(1,nodecnt+1);
    matrix trans(nodecnt+1,nodecnt+1);

    for(int i=0;i<=nodecnt;i++){
        for(int r=0;r<26;r++){
            int z=t[i].ch[r];
            if(find(z)) continue;
            trans[i][z]+=1;
        }
    }

    v[0][0]=1;
    while(n){
        if(n&1) v=v*trans;
        trans=trans*trans;
        n>>=1;
    }

    modint sum=0;
    for(int i=0;i<=nodecnt;i++) sum+=v[0][i];
    cout<<sum<<"\n";

    # ifdef KarmaticEnding
    cerr<<"\n\033[1;38;2;234;200;225mUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\033[0m\n";
    # endif
    return 0;
}

:::