HDU 2243 考研路茫茫——单词情结 AC自动机矩阵快速幂

2019-11-08 00:52:43

字体：大中小

来源：转载

供稿：网友

与POJ2778类似不同的是本题还要求和做法是为矩阵增加一行与一列结果减去1即为答案

[A 1] * [A 1] = [A^2 A+1][0 1] [0 1] [0 1 ][A 1] ^ k = [A^k A^1 + A^2 +...A^(k-1) + 1][0 1] [0 1 ]

A可以为一个数/矩阵

#include <cstdio>#include <algorithm>#include <cstring>#include <queue>#define LL unsigned long long//用unsigned long long存值省去对2^64取模#define N 30#define MAXN 55using namespace std;int n,m;char a[N];struct mat{ int n; LL a[N][N]; mat(int len) { n=len; memset(a,0,sizeof(a)); } mat Operator *(const mat &t) { mat tmp=mat(n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) tmp.a[i][j]+=a[i][k]*t.a[k][j]; return tmp; } void PRint() { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) printf("%llu ",a[i][j]); printf("/n"); } printf("----/n"); }};struct Trie{ int cnt,root; int nx[MAXN][26],fail[MAXN]; bool end[MAXN]; int f(char a){return a-'a';} int newnode() { cnt++; for(int i=0;i<26;i++) nx[cnt][i]=0; fail[cnt]=end[cnt]=0; return cnt; } void init() { cnt=0; root=newnode(); } void insert(char *s) { int len=strlen(s),now=root; for(int i=0;i<len;i++) { if(!nx[now][f(s[i])]) nx[now][f(s[i])]=newnode(); now=nx[now][f(s[i])]; } end[now]++; } void build_fail() { queue<int> q; fail[root]=root; for(int i=0;i<26;i++) { if(!nx[root][i]) nx[root][i]=root; else fail[nx[root][i]]=root,q.push(nx[root][i]); } while(!q.empty()) { int now=q.front(); if(end[fail[now]]) end[now]=1; for(int i=0;i<26;i++) { if(nx[now][i]) { fail[nx[now][i]]=nx[fail[now]][i]; q.push(nx[now][i]); } else nx[now][i]=nx[fail[now]][i]; } q.pop(); } return; } mat get_mat() { mat t=mat(cnt+1); for(int i=1;i<=cnt;i++) { if(end[i]) continue; for(int j=0;j<26;j++) if(!end[nx[i][j]]) t.a[i][nx[i][j]]++; } for(int i=1;i<=cnt+1;i++) t.a[i][cnt+1]=1; return t; }}AC;mat fpow(mat x,int k){ mat ans=mat(x.n); for(int i=1;i<=n;i++) ans.a[i][i]=1; while(k) { if(k&1) ans=ans*x; k=k>>1; x=x*x; } return ans;}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { AC.init(); for(int i=1;i<=n;i++) { scanf("%s",a); AC.insert(a); } AC.build_fail(); mat t1=fpow(AC.get_mat(),m); mat t2=mat(2); t2.a[1][1]=26; t2.a[1][2]=1; t2.a[2][2]=1; t2=fpow(t2,m); // t2.print(); LL ans=t2.a[1][2]+t2.a[1][1]-1; for(int i=1;i<=t1.n;i++) ans-=t1.a[1][i]; ans++; printf("%llu/n",ans); } return 0;}

上一篇：欢迎使用CSDN-markdown编辑器

下一篇：17-02-06