【AC自动机】【矩阵乘法】【等比数列】hdu2243 考研路茫茫——单词情结

题解：http://blog.csdn.net/xingyeyongheng/article/details/10005923

这里采用了二分法求等比数列前n项和。

等比数列前n项和也可以用矩乘快速幂来求[a 1]    [Sn]    =    [Sn+1]

　　　　　　　　　　　　　　　　　　  [0 1]    [a  ]          [   a   ]

#include<cstdio>

#include<cstring>

#include<vector>

#include<queue>

#include<iostream>

using namespace std;

typedef unsigned long long ull;

typedef vector<ull> vec;

typedef vector<vec> mat;

typedef pair<mat,mat> Point2;

typedef pair<ull,ull> Point;

int N;

mat I;

mat operator * (const mat &a,const mat &b)

{

    mat c(N,vec(N));

    for(int i=0;i<N;++i)

      for(int j=0;j<N;++j)

        for(int k=0;k<N;++k)

          c[i][j]=c[i][j]+a[i][k]*b[k][j];

    return c;

}

mat operator - (const mat &a,const mat &b)

{

    mat c(N,vec(N));

    for(int i=0;i<N;++i)

      for(int j=0;j<N;++j)

        c[i][j]=a[i][j]-b[i][j];

    return c;

}

mat operator + (const mat &a,const mat &b)

{

    mat c(N,vec(N));

    for(int i=0;i<N;++i)

      for(int j=0;j<N;++j)

        c[i][j]=a[i][j]+b[i][j];

    return c;

}

Point sum_a_n(ull a,ull n)

{

	if(n==0)

	  return Point(1,1);

	Point t=sum_a_n(a,n>>1);

	if(n&1)

	  return Point(t.first*t.first*a,t.second*(t.first*a+1));

	else

	  return Point(t.first*t.first,(t.second-t.first)*(t.first*a+1)+t.first);

}

Point2 sum_A_n(mat a,ull n)

{

	if(n==0)

	  return Point2(I,I);

	Point2 t=sum_A_n(a,n>>1);

	if(n&1)

	  return Point2(t.first*t.first*a,t.second*(t.first*a+I));

	else

	  return Point2(t.first*t.first,(t.second-t.first)*(t.first*a+I)+t.first);

}

queue<int>q;

int child[40][26],fail[40],size=1;

bool word[40];

void Insert(char S[])

{

    int len=strlen(S);

    int now=0;

    for(int i=0;i<len;++i)

      {

        if(!child[now][S[i]-'a'])

          child[now][S[i]-'a']=size++;

        now=child[now][S[i]-'a'];

      }

    word[now]=1;

}

void build()

{

    fail[0]=-1;

    q.push(0);

    while(!q.empty())

      {

        int U=q.front(); q.pop();

        for(int i=0;i<26;++i)

          if(child[U][i])

            {

              int V=fail[U];

              while(V!=-1)

                {

                  if(child[V][i])

                    {

                      fail[child[U][i]]=child[V][i];

                      break;

                    }

                  V=fail[V];

                }

              if(V==-1)

                fail[child[U][i]]=0;

              if(word[fail[child[U][i]]])

                word[child[U][i]]=1;

              q.push(child[U][i]);

            }

          else if(U)

            child[U][i]=child[fail[U]][i];

      }

}

int n,ma2[40];

ull m;

void Init()

{

	memset(child,0,sizeof(child));

	memset(fail,0,sizeof(fail));

	memset(word,0,sizeof(word));

	N=0;

	size=1;

}

int main()

{

	//freopen("hdu2243.in","r",stdin);

    char s[8];

    while(cin>>n>>m){

    Init();

    for(int i=1;i<=n;++i)

      {

        scanf("%s",s);

        Insert(s);

      }

    build();

    for(int i=0;i<size;++i)

      if(!word[i])

        ma2[i]=N++;

    I.assign(N,vec(N));

    for(int i=0;i<N;++i)

      I[i][i]=1;

    mat A(N,vec(N));

    for(int i=0;i<size;++i)

      for(int j=0;j<26;++j) if((!word[i]) && (!word[child[i][j]]))

        ++A[ma2[i]][ma2[child[i][j]]];

    A=sum_A_n(A,m).second-I;

    ull ans=sum_a_n(26,m).second-1;

    for(int i=0;i<N;++i)

      ans=ans-A[0][i];

    cout<<ans<<endl;

	}

    return 0;

}