hdu 2243 poj 2778 AC自動機 + 經典矩陣乘法

兩個題差不多，隻不過ｈｄｕ上的惡心一點，對２^64取模，其實就相當于不用取模，所有的數都用unsigned __int64 即可，注意，無符号類型6-9就不是-3了哦

經典矩陣乘法是指求A+A^2+A^3+A^4+....A^n

做法在這裡http://blog.csdn.net/haha593572013/article/details/8001943

然後這兩題主要要做的就是構造trie圖，繼而構造出初始矩陣，mat[i][j]表示i走到j有幾種走法 ，這個矩陣自乘n次之後就表示i走到j走n步有幾種走法

hdu  2243

#include<cstdio>
#include<cstring>
typedef unsigned __int64 ULL;
const int MAX = 65;
int n,k,m,tn;
struct  Mat {
    ULL mat[MAX][MAX];
    friend Mat operator *(Mat a,Mat b);
    friend Mat operator +(Mat a,Mat b);
    friend Mat operator ^(Mat a,int k);
}E,A;
ULL a[MAX][MAX];
Mat operator +(Mat a,Mat b)
{
    Mat c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            c.mat[i][j]=(a.mat[i][j]+b.mat[i][j]);
    return c;
}
Mat operator *(Mat a,Mat b)
{
    Mat ans;
    memset(ans.mat,0,sizeof(ans.mat));
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            for(int k=0;k<n;k++)
            {
                ULL tmp=a.mat[i][k]*b.mat[k][j];
                ans.mat[i][j]=ans.mat[i][j]+tmp;
            }
            return ans;
}
Mat operator ^(Mat a,int k)
{
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) E.mat[i][j]= (i==j);
    Mat ans=E;
    while(k){
        if(k&1) ans=ans*a;
        a=a*a,k>>=1;
    }
    return ans;
}
const int M = 100;
const int CD = 26;
int fail[M];
int Q[M];
int ch[M][CD];
int ID[128];
int sz;
int flag[M];
void Init() 
{
    fail[0]=0;
    memset(ch[0],0,sizeof(ch[0]));
    sz=1;
    for(int i=0;i<26;i++) ID[i+'a']=i;
}
void Insert(char *s)
{
    int p=0;
    for(;*s;s++)
    {
        int c=ID[*s];
        if(!ch[p][c])
        {
            memset(ch[sz],0,sizeof(ch[sz]));
            flag[sz]=0;
            ch[p][c]=sz++;
        }
        p=ch[p][c];
    }
    flag[p]=1;
}
void Construct()
{
    int *s=Q,*e=Q,v;
    for(int i=0;i<CD;i++)
    {
        if(ch[0][i])
        {
            fail[ch[0][i]]=0;
            *e++ = ch[0][i];
        }
    }
    while(s!=e)
    {
        int u = *s++;
        for(int i=0;i<CD;i++)
        {
            if(v=ch[u][i])
            {
                *e++=v;
                fail[v]=ch[fail[u]][i];
                flag[v]|=flag[fail[v]];
            }
            else 
            {
                ch[u][i]=ch[fail[u]][i];
            }
        }
    }
}
void init()
{
    memset(A.mat,0,sizeof(A.mat));
    for(int i=0;i<tn;i++)
    {
        for(int j=0;j<tn;j++)
        {
            A.mat[i][j]=a[i][j];
            A.mat[i][j+tn]=a[i][j];
        }
    }
    for(int i=tn;i<n;i++)
    {
        for(int j=tn;j<n;j++)
        {
            if(i==j)A.mat[i][j]=1;
        }
    }
}
int main()
{    
    int N;
    int L;
    char s[10];
    while(scanf("%d%d",&N,&L)!=EOF)
    {
        memset(a,0,sizeof(a));
        tn=1;  a[0][0]=26;   n=2*tn; init();
        Mat ans=A^L;
        ULL sum=ans.mat[0][1];
        Init();
        for(int i=0;i<N;i++)
        {
            scanf("%s",s);
            Insert(s);
        }
        Construct();
        Mat dp;
        memset(dp.mat,0,sizeof(dp.mat));
        for(int i=0;i<sz;i++)if(!flag[i])
        {
            for(int j=0;j<CD;j++) if(!flag[ch[i][j]])
            {
                dp.mat[i][ch[i][j]]++;
            }
        }
        memset(a,0,sizeof(a));
        for(int i=0;i<sz;i++)
        {
            for(int j=0;j<sz;j++)
            {
                a[i][j]=dp.mat[i][j];
            }
        }
        tn=sz; n=2*tn;   init();
        ans=A^L;
        ULL sum2=0;
        for(int j=tn;j<n;j++)
        {
            sum2+=ans.mat[0][j];
        }
        printf("%I64u\n",(sum-sum2));
    }
    return 0;
}
           

poj  2778

#include <cstdio>
#include <cstdlib>
#include <string>
#include <climits>
#include <iostream>   
#include <vector>
#include <set>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <sstream>
#include <map>
#include <cstring>
#include <queue>
using namespace std;
const int mod = 100000;
const int M = 100;
const int CD = 4;
int fail[M];
int Q[M];
int ch[M][CD];
int ID[128];
int val[M];
int sz;
void Init(){
	fail[0]=0;
	memset(ch[0],0,sizeof(ch[0]));
	sz=1;
	ID['A']=0;ID['T']=1;ID['G']=2;ID['C']=3;
}
void Insert(char *s){
	int p=0;
	for(;*s;s++){
		int c=ID[*s];
		if(!ch[p][c]){
			memset(ch[sz],0,sizeof(ch[sz]));
			val[sz]=0;
			ch[p][c]=sz++;
		}
		p=ch[p][c];
	}
	val[p]=1;
}
void Construct(){
	int  *s=Q,*e=Q;
	for(int i=0;i<CD;i++){
		if(ch[0][i]){
			fail[ch[0][i]] = 0;
			*e++ = ch[0][i];
		}
	}
	while(s!=e){
		int u = *s++;
		for(int i=0;i<CD;i++){
			int &v = ch[u][i];
			if(v){
				*e++ = v;
				fail[v]=ch[fail[u]][i];
				val[v]|=val[fail[v]];
			} else  {
				v=ch[fail[u]][i];
			}
		}
	}
}
long long dp[100][100];
const int MAX = 100;
int n;
struct  Mat {
	int mat[MAX][MAX];
	Mat(){
		memset(mat,0,sizeof(mat));
	}
	void init(){
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
              mat[i][j]= i==j;
	}
	void print(){
		printf("****************\n");
		for(int i=0;i<n;i++) 
			for(int j=0;j<n;j++)
			   printf(j==n-1?"%d\n":"%d ",mat[i][j]);
		printf("fuckfuckfuckfuckfuck\n");
	}
	friend Mat operator *(Mat a,Mat b);
	friend Mat operator +(Mat a,Mat b);
	friend Mat operator ^(Mat a,int k);
}E;
Mat operator +(Mat a,Mat b)
{
	Mat c;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			c.mat[i][j]=a.mat[i][j]+b.mat[i][j];
			if(c.mat[i][j]>=mod) c.mat[i][j]-=mod;
		}

	return c;
}
Mat operator *(Mat a,Mat b)
{
	Mat ans;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			long long tmp=0;
			for(int k=0;k<n;k++)
			{
				tmp+=(long long)a.mat[i][k]*b.mat[k][j];
			}
			ans.mat[i][j]=tmp%mod;
		}
	 
	return ans;
}
Mat operator ^(Mat a,int k)
{
	Mat ans=E;
	while(k){
		if(k&1) ans=ans*a;
		a=a*a,k>>=1;
	}
	return ans;
}
int main() {
	char s[15];
	int k,m;
	while(scanf("%d%d",&m,&k)!=EOF)	{
		Init();
		for(int i=0;i<m;i++)  {
			scanf("%s",s);
			Insert(s);
		}
		Construct();
		n=sz;
		Mat ans;
		for(int i=0;i<sz;i++)if(!val[i])
		{
			for(int j=0;j<4;j++) if(!val[ch[i][j]])
			{
                 ans.mat[i][ch[i][j]]++;
			}
		}
		//ans.print();
		E.init();
		ans=ans^k;
		//ans.print();
		int ret=0;
		for(int i=0;i<n;i++)
		{
			ret+=ans.mat[0][i];
			if(ret>=mod) ret-=mod;
		}
		printf("%d\n",ret);
	}
	return 0;
}