Censored!

Censored!

其实这题的思路也大同小异，利用AC自动机建 trie 图之后，构建可达矩阵，可达矩阵 m 次方后，第一行的值就是答案。需要注意，这个题的答案很大，需要用到高精度，所以把高精度跟矩阵乘法结合即可。

如果单纯只是这样的话，先会 re 然后再 t，wa 是因为读入的字符串的范围是\([33,255]\)，所以不能单纯用数组来存，需要用 map 来进行保存。

此外因为高精度乘法，再加上\(n^3\)的矩阵乘法，导致复杂度过大，所以会 t。观察发现，我们只用到了 ans 矩阵的第一行，所以可以只计算第一行的值即可，这样矩阵乘法就少了一个 n 的复杂度。

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#define mst(name, value) memset(name,value,sizeof(name))
using namespace std;


int MAXN=9999;
const int maxsize=30;
int dlen=4;
class BigNum {
public:
    int a[maxsize];
    int len;
public:
    BigNum() {
        len = 1;
        memset(a,0,sizeof(a));
    }
    BigNum(const int b) {
        int c,d = b;
        len = 0;
        memset(a,0,sizeof(a));
        while (d > MAXN) {
            c = d - (d / (MAXN + 1)) * (MAXN + 1);
            d = d / (MAXN + 1);
            a[len++] = c;
        }
        a[len++] = d;
    }
    BigNum operator+(const BigNum & T) const {
        BigNum t(*this);
        int i,big;
        big = T.len > len ? T.len : len;
        for (i = 0 ; i < big ; i++) {
            t.a[i] +=T.a[i];
            if (t.a[i] > MAXN) {
                t.a[i + 1]++;
                t.a[i] -=MAXN+1;
            }
        }
        if (t.a[big] != 0) t.len = big + 1;
        else t.len = big;
        return t;
    }
    BigNum operator*(const BigNum & T) const {
        BigNum ret;
        int i,j,up,temp,temp1;
        for (i = 0 ; i < len ; i++) {
            up = 0;
            for (j = 0 ; j < T.len ; j++) {
                temp = a[i] * T.a[j] + ret.a[i + j] + up;
                if (temp > MAXN) {
                    temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
                    up = temp / (MAXN + 1);
                    ret.a[i + j] = temp1;
                } else {
                    up = 0;
                    ret.a[i + j] = temp;
                }
            }
            if (up != 0)
                ret.a[i + j] = up;
        }
        ret.len = i + j;
        while (ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
        return ret;
    }


};
ostream& operator<<(ostream& out,BigNum& b) {
    int i;
    cout<<b.a[b.len-1];
    for(i=b.len-2; i>=0; --i) {
        cout.width(dlen);
        cout.fill(‘0‘);
        cout<<b.a[i];
    }
    return out;
}
typedef vector<BigNum> vec;
typedef vector<vec> mat;

mat operator *(mat &a,mat &b){
    mat ans(a.size(),vec(b[0].size(),0));
    for(int i=0;i<=0;++i)
        for(int j=0;j<b[0].size();++j)
            for(int k=0;k<b.size();++k)
                ans[i][j]=ans[i][j]+a[i][k]*b[k][j];
    return ans;
}

const int maxn=105;
namespace ac {
    const int chsiz=300;
    int fail[maxn],end[maxn];
    map<char,int> next[maxn];
    int root,sz;
    int newcode(char s[],int &slen) {
        for(int i=0; i<slen; ++i)
            next[sz][s[i]]=-1;
        end[sz++]=0;
        return sz-1;
    }
    void init(char s[],int &slen) {
        sz=0;
        root=newcode(s,slen);
    }
    void insert(char buf[],char s[],int &slen) {
        int len=strlen(buf);
        int now=root;
        for(int i=0; i<len; ++i) {
            if(next[now][buf[i]]==-1)
                next[now][buf[i]]=newcode(s,slen);
            now=next[now][buf[i]];
        }
        end[now]++;
    }
    void build(char s[],int &slen) {
        queue<int> q;
        fail[root]=root;
        for(int i=0; i<slen; ++i) {
            if(next[root][s[i]]==-1)
                next[root][s[i]]=root;
            else {
                fail[next[root][s[i]]]=root;
                q.push(next[root][s[i]]);
            }
        }
        while(q.size()) {
            int now=q.front();
            q.pop();
            end[now]|=end[fail[now]];
            for(int i=0; i<slen; ++i) {
                if(next[now][s[i]]==-1)
                    next[now][s[i]]=next[fail[now]][s[i]];
                else {
                    fail[next[now][s[i]]]=next[fail[now]][s[i]];
                    q.push(next[now][s[i]]);
                }
            }
        }
    }
    mat getmat(char s[],int &slen) {
        mat ans(sz,vec(sz,0));
        for(int i=0; i<sz; ++i) {
            for(int j=0; j<slen; ++j)
                if(!end[next[i][s[j]]])
                    ans[i][next[i][s[j]]]=ans[i][next[i][s[j]]]+1;
        }
        return ans;
    }
}

char s[maxn],buf[maxn];
int main() {
    int n,m,p;
    scanf("%d%d%d",&n,&m,&p);
    scanf("%s",s);
    ac::init(s,n);
    for(int i=1; i<=p; ++i) {
        scanf("%s",buf);
        ac::insert(buf,s,n);
    }
    ac::build(s,n);
    mat k=ac::getmat(s,n);

    mat ans=k;
    for(int i=1;i<m;++i)
        ans=ans*k;
    BigNum sum=0;
    for(int i=0; i<ac::sz; ++i)
        sum=sum+ans[0][i];
    cout<<sum<<endl;

    return 0;
}

Censored!

原文：https://www.cnblogs.com/CADCADCAD/p/14082360.html