|
|
Posted on 2010-10-30 23:40 Uriel 阅读(1268) 评论(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;
}
|