|
Posted on 2010-10-30 23:40 Uriel 阅读(1269) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 DP 、 字符串处理
第二道AC自动机,对DP状态转移有一点感觉了。。。 这题基本和2778一样,不过要高精度,所以就想用JAVA试试,正好JAVA很久不碰了,跟没学过一样,Regional之前练习练习,结果做得我痛不欲生。。00:00-03:10,06:50-09:00一直在整JAVA,先是不会用Class,翻书+上网搜+乱搞,终于不报错。。然后发现对象数组初始化又有问题。。然后函数又有问题。。各种纠结之后。。TLE。。方法是构造AC自动机,求状态转移矩阵,然后二分矩阵链乘。。TLE之后乱搞了一下没什么效果。。只好放弃。。 搜到某大牛Blog说这题矩阵链乘会爆栈,于是没敢写,跟网上大部分代码一样直接DP了(滚动数组),晚上终于AC。。 这是TLE的JAVA代码,不知道怎么改,还是说这种方法过不了,欢迎路过的大牛指教
//Problem: 1625 User: Uriel //Memory: N/A Time: N/A //Language: Java Result: Time Limit Exceeded
import java.util.*; import java.math.BigInteger;
class Node{ public int fail; public int nxt[]=new int[51]; public int cnt; public void init(){ for(int i=0;i<51;++i)nxt[i]=-1; } }
public class Main { static int kind,nnode,n,m,len,head,tail; static char s[]=new char[51]; static char word[]=new char[11]; static int d[]=new int[260]; static int que[]=new int[300]; static BigInteger mtx[][]=new BigInteger[300][300]; static BigInteger g[][]=new BigInteger[300][300]; static Node q[]=new Node[300]; static int gg[][]=new int[300][300]; public static void insert(){ int i,p=0; for(i=0;i<len;++i){ if(q[p].nxt[d[s[i]]]==-1){ nnode++; q[p].nxt[d[s[i]]]=nnode; q[nnode]=new Node(); q[nnode].init(); } if (q[p].cnt>0) break; p=q[p].nxt[d[s[i]]]; } q[p].cnt++; }
public static void build_ac_automation(){ int tmp,p,i; que[tail++]=0; while(head<tail){ tmp=que[head++]; for(i=0;i<kind;++i){ if(q[tmp].nxt[i]!=-1){ if(tmp==0)q[q[tmp].nxt[i]].fail=0; else{ p=q[tmp].fail; while(p!=-1){ if(q[p].nxt[i]!=-1){ q[q[tmp].nxt[i]].fail=q[p].nxt[i]; if(q[q[p].nxt[i]].cnt>0) q[q[tmp].nxt[i]].cnt++; break; } p=q[p].fail; } if(p==-1)q[q[tmp].nxt[i]].fail=0; } que[tail++]=q[tmp].nxt[i]; } } } }
public static void build_adj(){ int i,j; for(i=0;i<nnode;++i) for(j=0;j<kind;++j)gg[i][j]=0; for(i=0;i<nnode;++i) if(q[i].cnt==0) for(j=0;j<kind;++j){ if(q[i].nxt[j]!=-1 && q[q[i].nxt[j]].cnt==0)gg[i][q[i].nxt[j]]++; else if(q[i].nxt[j]==-1){ if(i==0)gg[0][0]++; else{ int tmp=i; while(q[tmp].nxt[j]==-1){ if(tmp==0)break; tmp=q[tmp].fail; } if(q[tmp].nxt[j]!=-1 && q[q[tmp].nxt[j]].cnt==0)gg[i][q[tmp].nxt[j]]++; else if(q[tmp].nxt[j]==-1 && tmp==0)gg[i][0]++; } } } }
public static void MatrixMul(BigInteger b[][],BigInteger c[][],int sz){ int i,j,k; BigInteger tmp[][]=new BigInteger[sz][sz]; for(i=0;i<sz;++i) for(j=0;j<sz;++j) tmp[i][j]=BigInteger.ZERO; for(i=0;i<sz;++i) for(j=0;j<sz;++j) for(k=0;k<sz;++k){ tmp[i][j]=tmp[i][j].add(b[i][k].multiply(c[k][j])); } for(i=0;i<sz;++i) for(j=0;j<sz;++j) b[i][j]=tmp[i][j]; }
public static void MatrixPow(BigInteger mtx[][],BigInteger a[][],int sz,int k){ while(k>0){ if(k%2==1)MatrixMul(mtx,a,sz); MatrixMul(a,a,sz); k>>=1; } }
public static void main(String[] args){ int i,j,m,n; Scanner stdin=new Scanner(System.in); kind=stdin.nextInt(); n=stdin.nextInt(); m=stdin.nextInt(); String ss=stdin.next(); word=ss.toCharArray(); len=ss.length(); for(i=0;i<len;++i)d[word[i]]=i; head=tail=0; nnode=0; q[0]=new Node(); q[0].init(); for(i=0;i<m;++i){ ss=stdin.next(); len=ss.length(); s=ss.toCharArray(); insert(); } build_ac_automation(); nnode++; build_adj(); for(i=0;i<nnode;++i) for(j=0;j<nnode;++j){ g[i][j]=BigInteger.valueOf(gg[i][j]); if(i==j)mtx[i][j]=BigInteger.ONE; else mtx[i][j]=BigInteger.ZERO; } MatrixPow(mtx,g,nnode,n); BigInteger ans=BigInteger.ZERO; for(i=0;i<nnode;++i)ans=ans.add(mtx[0][i]); System.out.println(ans); } }
下面是AC的C++代码,高精度乘法部分参考了网上某大牛的写法,AC自动机我的模板异常的慢,但是不知道怎么改了。。也希望路过的大牛指教。。
//Problem: 1625 User: Uriel //Memory: 496K Time: 422MS //Language: G++ Result: Accepted
#include<stdio.h> #include<stdlib.h> #include<string.h> #define max(x,y) (x>y?x:y)
struct node{ int fail; int nxt[51]; int cnt; void init(){ fail=-1; cnt=0; memset(nxt,-1,sizeof(nxt)); } }q[1010];
struct BigInt{ int a[100]; }f[2][105];
int nnode,n,m,maxl,ans[105]; int head,tail; int d[300],que[300];
void insert(char *s){ int i,p=0; for(i=0;s[i];++i){ if(q[p].nxt[d[s[i]]]==-1){ nnode++; q[p].nxt[d[s[i]]]=nnode; q[nnode].init(); } if(q[p].cnt)break; p=q[p].nxt[d[s[i]]]; } q[p].cnt++; }
void build_ac_automation(){ int tmp,p,i,j; que[tail++]=0; while(head<tail){ tmp=que[head++]; for(i=0;i<maxl;++i){ if(~q[tmp].nxt[i]){ if(!tmp)q[q[tmp].nxt[i]].fail=0; else{ p=q[tmp].fail; while(~p){ if(~q[p].nxt[i]){ q[q[tmp].nxt[i]].fail=q[p].nxt[i]; if(q[q[p].nxt[i]].cnt) q[q[tmp].nxt[i]].cnt++; break; } p=q[p].fail; } if(p==-1)q[q[tmp].nxt[i]].fail=0; } que[tail++]=q[tmp].nxt[i]; } } } }
void add(int a[105],int b[105]){ int c[105],i; memset(c,0,sizeof(c)); int Len=max(a[0],b[0]); for(i=a[0]+1;i<=Len;i++)a[i]=0; for(i=b[0]+1;i<=Len;i++)b[i]=0; for(i=1;i<=Len;i++){ c[i]=c[i-1]/10+a[i]+b[i]; c[i-1]=c[i-1]%10; } c[0]=Len; while(c[c[0]]>=10){ c[0]++; c[c[0]]=c[c[0]-1]/10; c[c[0]-1]=c[c[0]-1] %10; } for(i=0;i<=c[0];i++)b[i]=c[i]; }
void solve() { int cur=0,i,j; for(i=0;i<nnode;i++) { if(!i)f[cur][i].a[0]=f[cur][i].a[1]=1; else f[cur][i].a[0]=1,f[cur][i].a[1]=0; } while(n--){ for(i=0;i<nnode;i++)f[1-cur][i].a[0]=1,f[1-cur][i].a[1]=0; for(i=0;i<nnode;i++){ if(q[i].cnt)continue; for(j=0;j<maxl;j++){ if(q[i].nxt[j]!=-1 && !q[q[i].nxt[j]].cnt){ add(f[cur][i].a,f[1-cur][q[i].nxt[j]].a); } else if(q[i].nxt[j]==-1){ if(!i)add(f[cur][i].a,f[1-cur][0].a); else{ int tp=i; while(q[tp].nxt[j]==-1){ if(!tp)break; tp=q[tp].fail; } if(~q[tp].nxt[j] && !q[q[tp].nxt[j]].cnt)add(f[cur][i].a,f[1-cur][q[tp].nxt[j]].a); else if(q[tp].nxt[j]==-1 && tp==0)add(f[cur][i].a,f[1-cur][0].a); } } } } cur=1-cur; } ans[0]=1,ans[1]=0; for(i=0;i<nnode;i++)add(f[cur][i].a,ans); for(i=ans[0];i>=1;i--)printf("%d",ans[i]); putchar(10); }
int main(){ int i; char s[110]; scanf("%d %d %d",&maxl,&n,&m); scanf("%s",s); memset(d,0,sizeof(d)); for(i=0;i<maxl;++i){ d[s[i]]=i; } head=tail=0; nnode=0; q[0].init(); while(m--){ scanf("%s",s); insert(s); } build_ac_automation(); nnode++; solve(); return 0; }
|