定义重载运算的时候一定要将矩阵初始化, 因为这个调了一上午......
- Code:
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<queue>
- #include<string>
- #define maxn 100000
- typedef long long ll;
- using namespace std;
- void setIO(string a){ freopen((a+".in").c_str(),"r",stdin); }
- char arr[maxn];
- int mod, nodes;
- struct matrix{
- int m[105][105];
- }mat;
- void init(matrix &c){ for(int i=0;i<=nodes;++i) c.m[i][i]=1; }
- void get(matrix &c) {for(int i=0;i<=nodes;++i) for(int j=0;j<=nodes;++j) c.m[i][j]=0;}
- void print(matrix a){
- for(int i=0;i<=nodes;++i){
- for(int j=0;j<=nodes;++j) printf("%d",a.m[i][j]);
- printf("\n");
- }
- }
- matrix operator*(matrix a,matrix b){
- matrix c;
- get(c);
- for(int i=0;i<=nodes;++i)
- for(int j=0;j<=nodes;++j)
- for(int k=0;k<=nodes;++k){
- c.m[i][j]+=((ll)a.m[i][k]*b.m[k][j])%mod;
- c.m[i][j]%=mod;
- }
- return c;
- }
- matrix power(matrix a,long long k){
- matrix ans;
- for(int i=0;i<=nodes;++i) ans.m[i][i]=1;
- while(k){
- if(k&1)ans=ans*a;
- a=a*a;
- k/=2;
- }
- return ans;
- }
- struct Automaton{
- #define sigma 4
- int get(char s){
- if(s=='A') return 0;
- if(s=='C') return 1;
- if(s=='T') return 2;
- if(s=='G') return 3;
- }
- int ch[maxn][sigma],tag[maxn],fail[maxn];
- void insert(char str[]){
- int n=strlen(str);
- int j=0;
- for(int i=0;i<n;++i){
- if(!ch[j][get(str[i])]) ch[j][get(str[i])]=++nodes;
- j=ch[j][get(str[i])];
- }
- tag[j]=1;
- }
- queue<int>Q;
- void build(){
- for(int i=0;i<sigma;++i) if(ch[0][i]) Q.push(ch[0][i]);
- while(!Q.empty()){
- int u=Q.front();Q.pop();
- if(tag[fail[u]]) tag[u]=1;
- for(int i=0;i<sigma;++i){
- int r=ch[u][i];
- if(!r) { ch[u][i]=ch[fail[u]][i]; continue; }
- fail[r]=ch[fail[u]][i];
- Q.push(r);
- }
- }
- for(int i=0;i<=nodes;++i)
- for(int j=0;j<sigma;++j)
- if(!tag[i]&&!tag[ch[i][j]]) mat.m[i][ch[i][j]]+=1;
- }
- }aho;
- int main(){
- //setIO("input");
- mod=100000;
- int m, ans=0; long long n;
- scanf("%d%lld",&m,&n);
- for(int i=1;i<=m;++i)scanf("%s",arr), aho.insert(arr);
- aho.build();
- matrix fin=power(mat,n);
- for(int i=0;i<=nodes;++i) ans=(ans+fin.m[0][i])%mod;
- printf("%d",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2833801.html