题目地址：http://poj.org/problem?id=2778
数据很大，二维数组开不下，所以第一次写用了滚动数组，但是TLE
代码如下：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
typedef long long LL;
const int letter=4;
const int INF=0x3f3f3f3f;
struct Node{Node *pChilds[letter],*pPrev;bool bBadNode;Node(){memset(pChilds,0,sizeof(pChilds));pPrev=NULL; bBadNode=false;}
}tree[100+5];
char patten[20+5];
LL d[2][100+5];
int nNode;
map<char,int> idx;
//d[i][j]要长度为i到达节点j，也即是tree[j] 字符串个数
void Insert(Node* root,char* s)
{for(int i=0;s[i];i++){if(root->pChilds[idx[s[i]]]==NULL)root->pChilds[idx[s[i]]]=tree+nNode++;root=root->pChilds[idx[s[i]]];}root->bBadNode=true;
}
void BuildDfa()
{for(int i=0;i<letter;i++)tree[0].pChilds[i]=tree+1;tree[1].pPrev=tree;tree[0].pPrev=NULL;queue<Node*> Q;Q.push(tree+1);while(!Q.empty()){Node* root=Q.front(); Q.pop();for(int i=0;i<letter;i++){Node* p=root->pChilds[i];if(p==NULL) continue;Node* pPrev=root->pPrev;while(pPrev!=NULL){if(pPrev->pChilds[i]!=NULL){p->pPrev=pPrev->pChilds[i];if(p->pPrev->bBadNode) p->bBadNode=true;break;}else pPrev=pPrev->pPrev;}Q.push(p);}}
}
int main()
{idx['A']=0;idx['T']=1,idx['G']=2,idx['C']=3;int N,M; cin>>M>>N; nNode=2;for(int i=0;i<M;i++){scanf("%s",patten);Insert(tree+1,patten);}BuildDfa();d[0][1]=1;for(int i=0;i<N;i++){memset(d[i%2^1],0,sizeof(d[0]));for(int j=1;j<nNode;j++){if(tree[j].bBadNode) continue;for(int k=0;k<letter;k++){Node* pPrev=tree+j;while(pPrev){if(pPrev->pChilds[k]!=NULL){if(pPrev->pChilds[k]->bBadNode) break;int son=pPrev->pChilds[k]-tree;d[i%2^1][son]+=d[i%2][j];if(d[i%2^1][son]>100000) d[i%2^1][son]-=100000;break;} pPrev=pPrev->pPrev;} } }}LL ans=0;for(int i=1;i<nNode;i++) {ans+=d[N%2][i];if(ans>100000) ans-=100000;} cout<<ans;return 0;
}
下面用矩阵优化
d[i][j]表示i节点到j节点的个数
也即是 d[i][j]=∑ d[i][k]+d[n][k]
这和矩阵的运算法则一样
所以直接矩阵快速幂n次就好了
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
typedef long long LL;
const int letter=4;
const int INF=0x3f3f3f3f;
struct Matrix{ LL a[100+5][100+5]; int r; // r*r Matrix(int r=100+5):r(r){memset(a,0,sizeof(a));} //初始化长 void MakeI(int x){ //变为x*E的单位矩阵 memset(a,0,sizeof(a)); for(int i=0;i<r;i++) a[i][i]=x; } Matrix operator * (const Matrix& m) { //矩阵乘法 Matrix result(r); for(int i=0;i<r;i++) for(int j=0;j<r;j++) { for(int k=0;k<r;k++) result.a[i][j]+=a[i][k]*m.a[k][j]; } return result; } Matrix operator % (const int p){ //矩阵对每个元素取余 Matrix result(*this); for(int i=0;i<r;i++) for(int j=0;j<r;j++) result.a[i][j]%=p; return result; } Matrix operator + (const Matrix& m){ //矩阵互相相加 Matrix result(r); for(int i=0;i<r;i++) for(int j=0;j<r;j++) result.a[i][j]=a[i][j]+m.a[i][j]; return result; } Matrix operator + (int n){ //加上个常数 Matrix result(r); result.MakeI(n); return *this+result; }
};
Matrix PowMod(const Matrix& m,int k,int p) //矩阵快速幂
{ //m^k mod p int r=m.r; Matrix result(r); result.MakeI(1); //变成单位矩阵 Matrix base=m; while(k){ if(k&1) result=result*base%p; base=base*base%p; k>>=1; } return result;
}
struct Node{Node *pChilds[letter],*pPrev;bool bBadNode;Node(){memset(pChilds,0,sizeof(pChilds));pPrev=NULL; bBadNode=false;}
}tree[100+5];
char patten[20+5];
int nNode;
map<char,int> idx;
//d[i][j] 指节点i到j的步数 i，j都是安全节点，且其中也不经过危险节点
void Insert(Node* root,char* s)
{for(int i=0;s[i];i++){if(root->pChilds[idx[s[i]]]==NULL)root->pChilds[idx[s[i]]]=tree+nNode++;root=root->pChilds[idx[s[i]]];}root->bBadNode=true;
}
void BuildDfa()
{for(int i=0;i<letter;i++)tree[0].pChilds[i]=tree+1;tree[1].pPrev=tree;tree[0].pPrev=NULL;queue<Node*> Q;Q.push(tree+1);while(!Q.empty()){Node* root=Q.front(); Q.pop();for(int i=0;i<letter;i++){Node* p=root->pChilds[i];if(p==NULL) continue;Node* pPrev=root->pPrev;while(pPrev!=NULL){if(pPrev->pChilds[i]!=NULL){p->pPrev=pPrev->pChilds[i];if(p->pPrev->bBadNode) p->bBadNode=true;break;}else pPrev=pPrev->pPrev;}Q.push(p);}}
}
int main()
{idx['A']=0;idx['T']=1,idx['G']=2,idx['C']=3;int N,M; cin>>M>>N; nNode=2;for(int i=0;i<M;i++){scanf("%s",patten);Insert(tree+1,patten);}BuildDfa();Matrix d(nNode);for(int i=1;i<nNode;i++){if(tree[i].bBadNode) continue;for(int j=0;j<letter;j++){Node* pPrev=tree+i;while(pPrev){if(pPrev->pChilds[j]!=NULL){if(pPrev->pChilds[j]->bBadNode) break;int son=pPrev->pChilds[j]-tree;d.a[i][son]++;if(d.a[i][son]>=100000) d.a[i][son]-=100000;break;} pPrev=pPrev->pPrev;} }} Matrix m=PowMod(d,N,100000);LL ans=0;for(int i=1;i<nNode;i++)if(!tree[i].bBadNode) {ans+=m.a[1][i];if(ans>=100000) ans-=100000;}cout<<ans;return 0;
}