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

考研路茫茫——单词情结

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6018 Accepted Submission(s): 2042

Problem Description
背单词，始终是复习英语的重要环节。在荒废了3年大学生涯后，Lele也终于要开始背单词了。
一天，Lele在某本单词书上看到了一个根据词根来背单词的方法。比如”ab”,放在单词前一般表示”相反，变坏，离去”等。

于是Lele想，如果背了N个词根，那这些词根到底会不会在单词里出现呢。更确切的描述是：长度不超过L，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个呢？这里就不考虑单词是否有实际意义。

比如一共有2个词根 aa 和 ab ，则可能存在104个长度不超过3的单词，分别为
(2个) aa,ab,
(26个)aaa,aab,aac…aaz,
(26个)aba,abb,abc…abz,
(25个)baa,caa,daa…zaa,
(25个)bab,cab,dab…zab。

这个只是很小的情况。而对于其他复杂点的情况，Lele实在是数不出来了，现在就请你帮帮他。

Input
本题目包含多组数据，请处理到文件结束。
每组数据占两行。
第一行有两个正整数N和L。(0<N<6,0<L<2^31)
第二行有N个词根，每个词根仅由小写字母组成，长度不超过5。两个词根中间用一个空格分隔开。

Output
对于每组数据，请在一行里输出一共可能的单词数目。
由于结果可能非常巨大，你只需要输出单词总数模2^64的值。

Sample Input
2 3
aa ab
1 2
a

Sample Output
104
52

题目链接：HDU 2243
题目要求至少出现一次的方案数，这样显然不好求我们可以转换成总方案数减去一次都不出现的方案数，然后将题目的字符串改用AC自动机建立邻接矩阵，假设当前长度为i，那么对答案的贡献就是$26^i$-(长度为$i$的字符串中一次都不出现给定串的方案数)，后者可以像POJ 2778一样用矩阵快速幂算，也就是说我们只要算出前者的前$l$项和，后者的前$l$项和然后作差就是答案了，但是前者实际上用等比数列求和公式会错，估计是取模是不支持除法的，由于前者是等比数列，根据其递推公式，用2*2的矩阵快速幂也可以算，也就是说全程矩阵快速幂就可以了。
以下式子中$S_i$为等比矩阵数列的前$i$项和，其首项是$A$，公比是$A$

$$第一项递推式： \begin{pmatrix} 26 & 26 \\ 0 & 0 \\ \end{pmatrix} \times \begin{pmatrix} 26 & 0 \\ 1 & 1 \\ \end{pmatrix}^{n-1} = \begin{pmatrix} \sum_{i=1}^{n}{26^i} & 26 \\ 0 & 0 \\ \end{pmatrix}\\ 第二项递推式： \begin{pmatrix} S_1 & A \\ O & O \\ \end{pmatrix} \times \begin{pmatrix} A & O \\ E & E \\ \end{pmatrix}^{n-1} = \begin{pmatrix} S_n & A \\ O & O \\ \end{pmatrix}$$

代码：

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
typedef unsigned long long ULL;
const double PI = acos(-1.0);
const int N = 70;
struct Trie
{
    int nxt[26];
    int fail, cnt;
    void init()
    {
        for (int i = 0; i < 26; ++i)
            nxt[i] = -1;
        fail = cnt = 0;
    }
} L[N];
int sz, M;
char s[N];

namespace AC
{
    void init()
    {
        sz = 0;
        L[sz++].init();
    }
    void ins(char s[], int len)
    {
        int u = 0;
        for (int i = 0; i < len; ++i)
        {
            int v = s[i] - 'a';
            if (L[u].nxt[v] == -1)
            {
                L[sz].init();
                L[u].nxt[v] = sz++;
            }
            u = L[u].nxt[v];
        }
        L[u].cnt = 1;
    }
    void build()
    {
        queue<int>Q;
        L[0].fail = 0;
        for (int i = 0; i < 26; ++i)
        {
            if (L[0].nxt[i] == -1)
                L[0].nxt[i] = 0;
            else
            {
                L[L[0].nxt[i]].fail = 0;
                Q.push(L[0].nxt[i]);
            }
        }
        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            int uf = L[u].fail;
            if (L[uf].cnt)
                L[u].cnt = 1;
            for (int i = 0; i < 26; ++i)
            {
                if (L[u].nxt[i] == -1)
                    L[u].nxt[i] = L[uf].nxt[i];
                else
                {
                    L[L[u].nxt[i]].fail = L[uf].nxt[i];
                    Q.push(L[u].nxt[i]);
                }
            }
        }
    }
}
struct Mat
{
    ULL A[N][N];
    void zero()
    {
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                A[i][j] = 0;
    }
    void one()
    {
        zero();
        for (int i = 0; i < N; ++i)
            A[i][i] = 1;
    }
    Mat operator*(const Mat &rhs)const
    {
        Mat c;
        c.zero();
        for (int i = 0; i < M; ++i)
        {
            for (int k = 0; k < M; ++k)
            {
                if (A[i][k])
                {
                    for (int j = 0; j < M; ++j)
                    {
                        if (rhs.A[k][j])
                            c.A[i][j] = c.A[i][j] + A[i][k] * rhs.A[k][j];
                    }
                }
            }
        }
        return c;
    }
    friend Mat operator^(Mat a, ULL b)
    {
        Mat r;
        r.one();
        while (b)
        {
            if (b & 1)
                r = r * a;
            a = a * a;
            b >>= 1;
        }
        return r;
    }
};
int main(void)
{
    int n, i, j;
    LL l;
    while (~scanf("%d%I64d", &n, &l))
    {
        AC::init();
        while (n--)
        {
            scanf("%s", s);
            int len = strlen(s);
            AC::ins(s, len);
        }
        Mat ans, mid;
        ans.zero();
        mid.zero();
        AC::build();
        //计算前l项等比数列的和
        M = 2;
        ULL sum = 0;
        ans.A[0][0] = 26;
        ans.A[0][1] = 26;
        mid.A[0][0] = 26;
        mid.A[1][0] = mid.A[1][1] = 1;
        ans  = ans * (mid ^ (l - 1));
        sum = ans.A[0][0];
        ans.zero();
        mid.zero();

        //计算前l项矩阵幂的和
        M = sz * 2;
        for (i = 0; i < sz; ++i)
        {
            for (j = 0; j < 26; ++j)
            {
                int v = L[i].nxt[j];
                if (L[v].cnt)
                    continue;
                ++ans.A[i][v];
            }
        }
        for (i = 0; i < sz; ++i)
        {
            for (j = sz; j < M; ++j)
            {
                ans.A[i][j] = ans.A[i][j - sz];
                mid.A[i][j - sz] = ans.A[i][j - sz];
            }
        }
        for (i = 0; i < sz; ++i)
            mid.A[i + sz][i] = mid.A[i + sz][i + sz] = 1;
        ans  = ans * (mid ^ (l - 1));
        for (i = 0; i < sz; ++i)
            sum -= ans.A[0][i];
        printf("%I64u\n", sum);
    }
    return 0;
}