ZOJ 2619 && HDU 3058

兩道AC自動機+高消的求期望問題

先說HDU 3058

[cpp]
#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <queue>  
#include <algorithm>  
#define N 110  
using namespace std; 
int next[N][8],flag[N],fail[N],pos,tot,id[N]; 
int n; 
char s[11]; 
double mat[110][110]; 
 
int newnode(){ 
    memset(next[pos],0,sizeof(next[pos])); 
    flag[pos]=fail[pos]=0; 
    return pos++; 
} 
 
void insert(){ 
    int p=0,i; 
    for(i=0;s[i];i++){ 
        int k=s[i]-'A'; 
        p=next[p][k]?next[p][k]:next[p][k]=newnode(); 
    } 
    flag[p]=1; 
} 
 
void makefail(){ 
    queue<int>q; 
    q.push(0); 
    while(!q.empty()){ 
        int u=q.front(); 
        q.pop(); 
        for(int i=0;i<n;i++){ 
            int v=next[u][i]; 
            if(v==0) next[u][i]=next[fail[u]][i]; 
            else q.push(v); 
            if(u && v){ 
                fail[v]=next[fail[u]][i]; 
                flag[v]|=flag[fail[v]]; 
            } 
        } 
    } 
} 
 
void make_mat(){ 
    int i,j; 
    tot=0; 
    memset(id,0,sizeof(id)); 
    for(i=0;i<pos;i++) 
        if(flag[i]==0) id[i]=tot++; 
    memset(mat,0,sizeof(mat)); 
    for(i=0;i<pos;i++){ 
        if(flag[i]==1)continue; 
        mat[id[i]][tot]=-n; 
        mat[id[i]][id[i]]=-n; 
        for(j=0;j<n;j++){ 
            int k=next[i][j]; 
            if(flag[k]==1)continue; 
            mat[id[i]][id[k]]+=1.0; 
        } 
    } 
} 
 
bool gauss(){ 
    int i,j,row,id; 
    double maxx; 
    for(row=0;row<tot;row++){ 
        maxx=fabs(mat[row][row]);id=row; 
        for(i=row+1;i<tot;i++) 
            if(fabs(mat[i][row]>maxx)){ 
                maxx=fabs(mat[i][row]); 
                id=i; 
            } 
        if(maxx<1e-11) return 0;    //我一開始這裡精度設置1e-8就WA死了。。。。。。  
        if(id!=row){ 
            for(j=0;j<=tot;j++) 
                swap(mat[row][j],mat[id][j]); 
        } 
        for(i=row+1;i<tot;i++){ 
            for(j=tot;j>=row;j--) 
                mat[i][j]-=mat[i][row]/mat[row][row]*mat[row][j]; 
        } 
    } 
    for(i=tot-1;i>=0;i--){ 
        for(j=i+1;j<tot;j++) 
            mat[i][tot]-=mat[i][j]*mat[j][j]; 
        mat[i][i]=mat[i][tot]/mat[i][i]; 
    } 
    return 1; 
} 
 
int main(){ 
    int t,T,m,i; 
    scanf("%d",&T); 
    for(t=1;t<=T;t++){ 
        scanf("%d %d",&n,&m); 
        pos=0,newnode(); 
        for(i=1;i<=m;i++){ 
            scanf("%s",s); 
            insert(); 
        } 
        makefail(); 
        make_mat(); 
        gauss(); 
        printf("%.2lf\n",mat[0][0]); 
    } 
} 

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#define N 110
using namespace std;
int next[N][8],flag[N],fail[N],pos,tot,id[N];
int n;
char s[11];
double mat[110][110];

int newnode(){
    memset(next[pos],0,sizeof(next[pos]));
    flag[pos]=fail[pos]=0;
    return pos++;
}

void insert(){
    int p=0,i;
    for(i=0;s[i];i++){
        int k=s[i]-'A';
        p=next[p][k]?next[p][k]:next[p][k]=newnode();
    }
    flag[p]=1;
}

void makefail(){
    queue<int>q;
    q.push(0);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<n;i++){
            int v=next[u][i];
            if(v==0) next[u][i]=next[fail[u]][i];
            else q.push(v);
            if(u && v){
                fail[v]=next[fail[u]][i];
                flag[v]|=flag[fail[v]];
            }
        }
    }
}

void make_mat(){
    int i,j;
    tot=0;
    memset(id,0,sizeof(id));
    for(i=0;i<pos;i++)
        if(flag[i]==0) id[i]=tot++;
    memset(mat,0,sizeof(mat));
    for(i=0;i<pos;i++){
        if(flag[i]==1)continue;
        mat[id[i]][tot]=-n;
        mat[id[i]][id[i]]=-n;
        for(j=0;j<n;j++){
            int k=next[i][j];
            if(flag[k]==1)continue;
            mat[id[i]][id[k]]+=1.0;
        }
    }
}

bool gauss(){
    int i,j,row,id;
    double maxx;
    for(row=0;row<tot;row++){
        maxx=fabs(mat[row][row]);id=row;
        for(i=row+1;i<tot;i++)
            if(fabs(mat[i][row]>maxx)){
                maxx=fabs(mat[i][row]);
                id=i;
            }
        if(maxx<1e-11) return 0;    //我一開始這裡精度設置1e-8就WA死了。。。。。。
        if(id!=row){
            for(j=0;j<=tot;j++)
                swap(mat[row][j],mat[id][j]);
        }
        for(i=row+1;i<tot;i++){
            for(j=tot;j>=row;j--)
                mat[i][j]-=mat[i][row]/mat[row][row]*mat[row][j];
        }
    }
    for(i=tot-1;i>=0;i--){
        for(j=i+1;j<tot;j++)
            mat[i][tot]-=mat[i][j]*mat[j][j];
        mat[i][i]=mat[i][tot]/mat[i][i];
    }
    return 1;
}

int main(){
    int t,T,m,i;
    scanf("%d",&T);
    for(t=1;t<=T;t++){
        scanf("%d %d",&n,&m);
        pos=0,newnode();
        for(i=1;i<=m;i++){
            scanf("%s",s);
            insert();
        }
        makefail();
        make_mat();
        gauss();
        printf("%.2lf\n",mat[0][0]);
    }
}

ZOJ 2619

具體數學上的結論題

[cpp]
#include <cstdio>  
#include <cstring>  
typedef long long ll; 
using namespace std; 
char s[410]; 
 
bool judge(int s1,int s2){ 
    while(s[s1] && s[s2]){ 
        if(s[s1]!=s[s2]) return 0; 
        s1++,s2++; 
    } 
    return 1; 
} 
 
int main(){ 
    int t,T; 
    int n,i; 
    ll ans; 
    scanf("%d",&T); 
    for(t=1;t<=T;t++){ 
        scanf("%d %s",&n,s); 
        ans=0; 
        for(i=0;s[i];i++){ 
            if(judge(0,i)) ans++; 
            ans*=n; 
        } 
        printf("Case %d:\n",t); 
        printf("%lld\n",ans); 
        if(t!=T)puts(""); 
    } 
} 

#include <cstdio>
#include <cstring>
typedef long long ll;
using namespace std;
char s[410];

bool judge(int s1,int s2){
    while(s[s1] && s[s2]){
        if(s[s1]!=s[s2]) return 0;
        s1++,s2++;
    }
    return 1;
}

int main(){
    int t,T;
    int n,i;
    ll ans;
    scanf("%d",&T);
    for(t=1;t<=T;t++){
        scanf("%d %s",&n,s);
        ans=0;
        for(i=0;s[i];i++){
            if(judge(0,i)) ans++;
            ans*=n;
        }
        printf("Case %d:\n",t);
        printf("%lld\n",ans);
        if(t!=T)puts("");
    }
}

高消的做法（注意這裡所有的變量都是整數，用long long的高消，用doube卡死精度）

[cpp]
#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <queue>  
#include <algorithm>  
#define N 110  
typedef long long ll; 
using namespace std; 
int next[N][26],flag[N],fail[N],pos,tot,id[N]; 
int n; 
char s[21]; 
ll mat[110][110]; 
 
int newnode(){ 
    memset(next[pos],0,sizeof(next[pos])); 
    flag[pos]=fail[pos]=0; 
    return pos++; 
} 
 
void insert(){ 
    int p=0,i; 
    for(i=0;s[i];i++){ 
        int k=s[i]-'A'; 
        p=next[p][k]?next[p][k]:next[p][k]=newnode(); 
    } 
    flag[p]=1; 
} 
 
void makefail(){ 
    queue<int>q; 
    q.push(0); 
    while(!q.empty()){ 
        int u=q.front(); 
        q.pop(); 
        for(int i=0;i<n;i++){ 
            int v=next[u][i]; 
            if(v==0) next[u][i]=next[fail[u]][i]; 
            else q.push(v); 
            if(u && v){ 
                fail[v]=next[fail[u]][i]; 
                flag[v]|=flag[fail[v]]; 
            } 
        } 
    } 
} 
 
void make_mat(){ 
    int i,j; 
    tot=0; 
    memset(id,0,sizeof(id)); 
    for(i=0;i<pos;i++) 
        if(flag[i]==0) id[i]=tot++; 
    memset(mat,0,sizeof(mat)); 
    for(i=0;i<pos;i++){ 
        if(flag[i]==1)continue; 
        mat[id[i]][tot]=-n; 
        mat[id[i]][id[i]]=-n; 
        for(j=0;j<n;j++){ 
            int k=next[i][j]; 
            if(flag[k]==1)continue; 
            mat[id[i]][id[k]]+=1; 
        } 
    } 
    /*printf("%d\n",tot);
    printf("Matrix has %d rows and %d columns\n",tot,tot+1);
    for(i=0;i<tot;i++){
        for(j=0;j<=tot;j++) printf("%lld\t",mat[i][j]);
        puts("");
    }
    puts("*******");*/ 
} 
 
ll gcd(ll a,ll b){ 
    if (b==0) 
        return a; 
    else return gcd(b,a%b); 
} 
 
bool gauss(){ 
    int i,j,row,id; 
    ll maxx; 
    for(row=0;row<tot;row++){ 
        maxx=abs(mat[row][row]),id=row;   //這裡要挑一個小的移動，如果還是大的後面會溢出 或者干脆不移動也可以  
        for(i=row+1;i<tot;i++) 
            if(abs(mat[i][row]<maxx) && mat[i][row]){ 
                maxx=abs(mat[i][row]); 
                id=i; 
            } 
        //if(maxx==0)continue;  
        if(id!=row){ 
            for(j=0;j<=tot;j++) 
                swap(mat[row][j],mat[id][j]); 
        } 
        for(i=row+1;i<tot;i++){ 
            if(mat[i][row]!=0){ 
                ll q=gcd(mat[i][row],mat[row][row]); 
                ll gb=mat[i][row]*mat[row][row]/q; 
                ll l1,l2; 
                l1=gb/mat[i][row]; 
                l2=gb/mat[row][row]; 
                for(j=row;j<=tot;j++) 
                   mat[i][j]=mat[i][j]*l1-mat[row][j]*l2; 
            } 
        } 
 
        /*for(i=0;i<tot;i++){
            for(j=0;j<=tot;j++) printf("%lld\t",mat[i][j]);
            puts("");
        }
        puts("*******");*/ 
 
    } 
    for(i=tot-1;i>=0;i--){ 
        for(j=i+1;j<tot;j++) 
            mat[i][tot]-=mat[i][j]*mat[j][j]; 
        mat[i][i]=mat[i][tot]/mat[i][i]; 
    } 
    return 1; 
} 
 
int main(){ 
    int t,T,m,i; 
    //freopen("a.txt","r",stdin);  
    //freopen("b.txt","w",stdout);  
    scanf("%d",&T); 
    for(t=1;t<=T;t++){ 
        scanf("%d",&n); 
        pos=0,newnode(); 
        scanf("%s",s); 
        insert(); 
        makefail(); 
        make_mat(); 
        gauss(); 
        printf("Case %d:\n",t); 
        printf("%lld\n",mat[0][0]); 
        if(t!=T) puts(""); 
    } 
}