HDU 2243 考研路茫茫――单词情结 ——（AC自动机+矩阵快速幂）

　　和前几天做的AC自动机类似。

　　思路简单但是代码200余行。。

　　假设solve_sub(i)表示长度为i的不含危险单词的总数。

　　最终答案为用总数（26^1+26^2+...+26^n）减去（solve_sub(1)+solve_sub(2)+...+solve_sub(n)）。前者构造f[i]=f[i-1]*26+26然后矩阵快速幂即可（当然也可以分治的方法）。后者即构造出dp矩阵p，然后计算（p^1+p^2+...+p^n），对其分治即可。

　　代码如下：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
const int MAX_Tot = 30 + 5;
const int mod = 100000;
typedef unsigned long long ull;

int m,n;

struct matrix
{
    ull e[MAX_Tot][MAX_Tot];
    int n,m;
    matrix() {}
    matrix(int _n,int _m): n(_n),m(_m) {memset(e,0,sizeof(e));}
    matrix operator * (const matrix &temp)const
    {
        matrix ret = matrix(n,temp.m);
        for(int i=1;i<=ret.n;i++)
        {
            for(int j=1;j<=ret.m;j++)
            {
                for(int k=1;k<=m;k++)
                {
                    ret.e[i][j] += e[i][k]*temp.e[k][j];
                }
            }
        }
        return ret;
    }
    matrix operator + (const matrix &temp)const
    {
        matrix ret = matrix(n,m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                ret.e[i][j] += e[i][j]+temp.e[i][j];
            }
        }
        return ret;
    }
    void getE()
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                e[i][j] = i==j?1:0;
            }
        }
    }
};

matrix qpow(matrix temp,int x)
{
    int sz = temp.n;
    matrix base = matrix(sz,sz);
    base.getE();
    while(x)
    {
        if(x & 1) base = base * temp;
        x >>= 1;
        temp = temp * temp;
    }
    return base;
}

matrix solve(matrix a, int k)
{
    if(k == 1) return a;
    int n = a.n;
    matrix temp = matrix(n,n);
    temp.getE();
    if(k & 1)
    {
        matrix ex = qpow(a,k);
        k--;
        temp = temp + qpow(a,k/2);
        return temp * solve(a,k/2) + ex;
    }
    else
    {
        temp = temp + qpow(a,k/2);
        return temp * solve(a,k/2);
    }
}

struct Aho
{
    struct state
    {
        int nxt[26];
        int fail,cnt;
    }stateTable[MAX_Tot];

    int size;

    queue<int> que;

    void init()
    {
        while(que.size()) que.pop();
        for(int i=0;i<MAX_Tot;i++)
        {
            memset(stateTable[i].nxt,0,sizeof(stateTable[i].nxt));
            stateTable[i].fail = stateTable[i].cnt = 0;
        }
        size = 1;
    }

    void insert(char *s)
    {
        int n = strlen(s);
        int now = 0;
        for(int i=0;i<n;i++)
        {
            char c = s[i];
            if(!stateTable[now].nxt[c-'a'])
                stateTable[now].nxt[c-'a'] = size++;
            now = stateTable[now].nxt[c-'a'];
        }
        stateTable[now].cnt = 1;
    }

    void build()
    {
        stateTable[0].fail = -1;
        que.push(0);

        while(que.size())
        {
            int u = que.front();que.pop();
            for(int i=0;i<26;i++)
            {
                if(stateTable[u].nxt[i])
                {
                    if(u == 0) stateTable[stateTable[u].nxt[i]].fail = 0;
                    else
                    {
                        int v = stateTable[u].fail;
                        while(v != -1)
                        {
                            if(stateTable[v].nxt[i])
                            {
                                stateTable[stateTable[u].nxt[i]].fail = stateTable[v].nxt[i];
                                // 在匹配fail指针的时候顺便更新cnt
                                if(stateTable[stateTable[stateTable[u].nxt[i]].fail].cnt == 1)
                                    stateTable[stateTable[u].nxt[i]].cnt = 1;
                                break;
                            }
                            v = stateTable[v].fail;
                        }
                        if(v == -1) stateTable[stateTable[u].nxt[i]].fail = 0;
                    }
                    que.push(stateTable[u].nxt[i]);
                }
                /*****建立自动机nxt指针*****/
                else
                {
                    if(u == 0) stateTable[u].nxt[i] = 0;
                    else
                    {
                        int p = stateTable[u].fail;
                        while(p != -1 && stateTable[p].nxt[i] == 0) p = stateTable[p].fail;
                        if(p == -1) stateTable[u].nxt[i] = 0;
                        else stateTable[u].nxt[i] = stateTable[p].nxt[i];
                    }
                }
                /*****建立自动机nxt指针*****/
            }
        }
    }

    matrix build_matrix()
    {
        matrix ans = matrix(size,size);
        for(int i=0;i<size;i++)
        {
            for(int j=0;j<26;j++)
            {
                if(!stateTable[i].cnt && !stateTable[stateTable[i].nxt[j]].cnt)
                    ans.e[i+1][stateTable[i].nxt[j]+1]++;
            }
        }
        return ans;
    }
}aho;

void print(matrix p)
{
    int n = p.n;
    int m = p.m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            printf("%d ",p.e[i][j]);
        }
        puts("");
    }
}

int main()
{
    while(scanf("%d%d",&m,&n) == 2)
    {
        aho.init();
        char s[15];
        for(int i=1;i<=m;i++)
        {
            scanf("%s",s);
            aho.insert(s);
        }
        aho.build();
        matrix p = aho.build_matrix();
        p = solve(p,n);
        ull temp = 0;
        for(int i=1;i<=aho.size;i++) temp += p.e[1][i];
        matrix t = matrix(1,2);
        t.e[1][2] = 1;
        matrix A = matrix(2,2);
        A.e[1][1] = A.e[2][1] = 26; A.e[2][2] = 1;
        t = t * qpow(A,n);
        ull ans = t.e[1][1] - temp;
        printf("%llu
",ans);
    }
    return 0;
}

　　最后觉得，，我之前矩阵模板里的print()真好用啊233= =。