[HDU 2243]考研路茫茫——单词情结

要計算有多少字包含任一個字根，我們可以先算出有多少字不包含任一個字根，然後再用全部的情況去扣掉

可以考慮把這些字根做成一個$AC$自動機
這樣一來，長度$n$不包含任何一個字根的單字數量就是在這個$AC$自動機裡面走$n$步沒有碰到結束集合的方法數了

可以發現，這個$AC$自動機的大小不會超過$5*5+1=26$ (根也要算進去)，因此可以直接利用矩陣快速冪計算走$n$步到達各個位置的方法數
設這個$AC$自動機的轉移矩陣是$A$

因此長度$\leq L$且不包含任一個字根的單字數量就是走$0$步、走$1$步、走$2$步、走$3$步、...、走$L$步的情況全部加起來
對應到的矩陣就是$A^{0}+A^{1}+A^{2}+A^{3}+...+A^{L}=\sum_{i=0}^{L}A^{i}$

直接算會超時

說明：
$Sum(n)=\sum_{i=0}^{n}A^{i}$
$M$為$A$的大小

可以發現，如果我們已經算出$Sum(n)$
再把它乘上$A^{0}+A^{n+1}$，就變成$Sum(2n+1)$了！

更精確地說，我們可以得到以下遞迴式：
$if$ $n$是奇數，$Sum(n)=Sum(\frac{n-1}{2})*(A^{0}+A^{\frac{n+1}{2}})$
$if$ $n$是偶數，$Sum(n)=Sum(n-1)*A^{n}$

算出$A^{n}$利用快速冪可以做到$O(M^{3}\log n)$
矩陣加法$O(M^{2})$
遞迴不會超過$O(\log n)$層
因此算出$Sum(n)$的時間複雜度就是$O((M^{3}\log n+M^{2})\log n)$了

注意答案不是$Sum(L)$，是所有情況減掉$Sum(L)$
所有情況的數量 ($\sum_{i=0}^{L}26^{i}$) 一樣可以依照以上方法計算出來
另外，題目要求$\mod 2^{64}$，因此只要在$unsigned\ long\ long$之下進行這些運算並自由讓它$over\ flow$即可

時間複雜度：$O(M^{3}\log^{2}L)$

code:

#include<cstdio>
#include<cassert>
#include<queue>
using namespace std;
typedef unsigned long long ULL;
int N,L;
struct Matrix
{
    ULL s[26][26];
    Matrix operator*(const Matrix &m)const
    {
        Matrix ans;
        for(int i=0;i<N;i++)for(int j=0;j<N;j++)
        {
            ULL &v=ans.s[i][j]=0;
            for(int k=0;k<N;k++)v+=s[i][k]*m.s[k][j];
        }
        return ans;
    }
    Matrix operator+(const Matrix &m)const
    {
        Matrix ans;
        for(int i=0;i<N;i++)for(int j=0;j<N;j++)ans.s[i][j]=s[i][j]+m.s[i][j];
        return ans;
    }
};
struct AC_Automaton
{
    int ch[26][26],sz;
    bool is_end[26];
    void Clear(){sz=0;Expand();}
    void Expand(){for(int i=0;i<26;i++)ch[sz][i]=0;is_end[sz++]=false;}
    int GetNxt(const int u,const int c)
    {
        if(ch[u][c]==0){Expand();ch[u][c]=sz-1;}
        return ch[u][c];
    }
    int GetID(const char c){return c-'a';}
    void Insert(const char *str)
    {
        int u=0;
        for(int i=0;str[i];i++)u=GetNxt(u,GetID(str[i]));
        is_end[u]=true;
    }
    int fail[101];
    void BuildFail()
    {
        fail[0]=0;
        queue<int>q;
        for(int i=0;i<26;i++)if(ch[0][i])fail[ch[0][i]]=0,q.push(ch[0][i]);
        while(!q.empty())
        {
            const int u=q.front();q.pop();
            for(int i=0;i<26;i++)if(ch[u][i])
            {
                int &f=fail[ch[u][i]]=fail[u];
                while(f&&ch[f][i]==0)f=fail[f];
                f=ch[f][i];
                is_end[ch[u][i]]|=is_end[f];
                q.push(ch[u][i]);
            }
        }
    }
    Matrix GetMatrix()
    {
        Matrix ans;
        N=sz;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)ans.s[i][j]=0;
            for(int c=0;c<26;c++)
            {
                int u=i;
                while(u&&ch[u][c]==0)u=fail[u];
                u=ch[u][c];
                if(is_end[u])continue;
                ans.s[i][u]++;
            }
        }
        return ans;
    }
}AC;
Matrix I()
{
    Matrix ans;
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)ans.s[i][j]=(i==j?1:0);
    return ans;
}
Matrix Pow(Matrix a,int p)
{
    Matrix ans=I();
    for(;p;a=a*a,p>>=1)if(p&1)ans=ans*a;
    return ans;
}
Matrix GetSum(const Matrix &m,const int n)
{
    if(n==0)return I();
    const int mid=((long long)n+1)/2;//notice n=2147483647
    const Matrix &ans=GetSum(m,mid-1)*(I()+Pow(m,mid));
    if(n&1)return ans;
    else return ans+Pow(m,n);
}
//  S=26^0+26^1+26^2+26^3+...+26^n
//26S=26^1+26^2+26^3+26^4+...+26^(n+1)
//25S=26^(n+1)-1
ULL Pow26(int p)
{
    ULL ans=1,a=26;
    for(;p;a*=a,p>>=1)if(p&1)ans*=a;
    return ans;
}
ULL GetSum(const int n)
{
    if(n==0)return 1;
    const int mid=((long long)n+1)/2;//notice n=2147483647
    const ULL &ans=GetSum(mid-1)*(1+Pow26(mid));
    if(n&1)return ans;
    else return ans+Pow26(n);
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&L)==2)
    {
        AC.Clear();
        for(int i=0;i<N;i++)
        {
            static char word[11];scanf("%s",word);
            AC.Insert(word);
        }
        AC.BuildFail();
        const Matrix &m=GetSum(AC.GetMatrix(),L);
        ULL ans=GetSum(L);
        for(int i=0;i<N;i++)ans-=m.s[0][i];
        printf("%llu\n",ans);
    }
    return 0;
}