AC自动机+dp状态压缩（练习）

hdu 2243

1.解释：

先构造矩阵A，$A^{n}A^n$表示含有词根长度为n的单词数量，长度不小于n且含词根的单词数量$X=A+A^2+\mathrm{.}\mathrm{.}\mathrm{.}+A^{n}X=A+A^2+...+A^n$，单词总数$sum=26+26\dots \dots 2+\mathrm{.}\mathrm{.}\mathrm{.}+26^{n}sum=26+26\dots \dots 2+...+26^n$,根据题意，需要求长度不小于n且不含词根的单词数量，则ans=sum-X;

可以参考二分幂的方法:先求出$(A+A^2+A^3\dots \dots A^{n\mathrm{/}2})(A+A^2+A^3\dots \dots A^\{n/2\})$【记为B】和$A^{n\mathrm{/}2}A^\{n/2\}$的值,则$X=(A^{n\mathrm{/}2}+E)\ast BX=(A^\{n/2\}+E)*B$,E为单位阵。算数的也是同样的方法。将运算过程中的变量和矩阵的元素定义为unsigned long long，就能实现自动对2^64自动取MOD.注意：因为我的代码是递归的形式，求完n/2，再求n，故要讨论n是奇还是偶

2.代码：

#include<cstdio>
#include<cstring>
#include<iostream> 
#include<queue>
#define ull unsigned long long
using namespace std;
int ch[35][26],f[35],sz;
int val[35];
struct Trie{
    Trie(){ sz = 0; memset(ch,0,sizeof(ch)); memset(val,0,sizeof val);};
    void insert(char *s){
        int u=0;
        for(int i=0;s[i];++i){
            int c=s[i]-&#39;a&#39;;
            if(!ch[u][c]) ch[u][c] = ++sz;
            u=ch[u][c];
        }
        val[u]=1;
    }
};
void getFail(){
    queue<int>q; int u;
    f[0] = 0;
    for(int c=0;c<26;++c){
        u = ch[0][c];
        if(u)  { f[u]=0; q.push(u);}
    }
    while(!q.empty()){
        int r=q.front(); q.pop();
        for(int c=0;c<26;++c){
            u=ch[r][c];
            if(!u){
                ch[r][c]=ch[f[r]][c];
                continue;
            }
            q.push(u);
            f[u] = ch[f[r]][c];
            val[u]|=val[ch[f[r]][c]];
        }
    }
}
struct mat {
    ull matrix[35][35];
    mat() {
        memset(matrix,0,sizeof(matrix));
    }
}a;
mat one() {
	mat res;
	for(int i=0; i<=sz; ++i) res.matrix[i][i]=1;
    return res;
}
mat zero() {
	mat res;
	memset(res.matrix,0,sizeof(res.matrix));
	return res;
}
mat operator*(const mat &m1,const mat &m2){
    mat m;
    for(int i=0; i<=sz; ++i){
        for(int j=0; j<=sz; ++j){
            for(int k=0; k<=sz; ++k){
                m.matrix[i][j]+=m1.matrix[i][k]*m2.matrix[k][j];
            }
        }
    }
    return m;
}
mat operator+(const mat &m1,const mat &m2){
    mat m;
    for(int i=0; i<=sz; ++i){
        for(int j=0; j<=sz; ++j){
                m.matrix[i][j]=m1.matrix[i][j]+m2.matrix[i][j];
        }
    }
    return m;
}
pair<ull,ull> bin(int k) {
	if(k==1)	return make_pair(26,26);
	else if(k==0)	return make_pair(0,1);
	pair<ull,ull> tmp,res;
	tmp=bin(k>>1);
	res.first=(tmp.second+(ull)1)*tmp.first;
	res.second=tmp.second*tmp.second;
	if(k&1) {
		res.second=res.second*26;
		res.first=res.first+res.second;
	}
	return res;
}
pair<mat,mat> bing(int k) {
	if(k==1)	return make_pair(a,a);
	else if(k==0)	return make_pair(zero(),one());
	pair<mat,mat> tmp,res;
	tmp=bing(k>>1);
	res.first=(tmp.second+one())*tmp.first;
	res.second=tmp.second*tmp.second;
	if(k&1) {
		res.second=res.second*a;
		res.first=res.first+res.second;
	}
	return res;
}
char str[6];
int n,l;
int main(){
    while(~scanf("%d%d",&n,&l)) {
    	Trie trie;  ull ans=0;
    	a=zero();
    	for(int i=0;i<n;++i) {
    		scanf("%s",str);
    		trie.insert(str);
		}
		getFail();
		for(int i=0;i<=sz;++i) {
			if(val[i])	continue;
			for(int j=0;j<26;++j) {
				if(val[ch[i][j]])	continue;
				++a.matrix[i][ch[i][j]];
			}
		}
		a=bing(l).first;
		for(int i=0;i<=sz;++i)	ans+=a.matrix[0][i];
		ans=bin(l).first-ans;
		printf("%llu\n",ans);
	}
}

（写了getfail函数却没有调用它，但是过了一些案例，一提交就wa，wa了一天，wa得明明白白的）

#include<bits/stdc++.h> 
#define mod 20090717
using namespace std;
int ch[105][26],f[105],sz,td,ans;
int val[105],dp[30][105][1024];
/*dp[i][j][k]中，k最大为(1<<m)-1*/
struct Trie{
    Trie(){ sz = 0; td=0; memset(ch,0,sizeof(ch)); memset(val,0,sizeof val);memset(dp,0,sizeof dp);};
    void insert(char *s){
        int u=0;
        for(int i=0;s[i];++i){
            int c=s[i]-&#39;a&#39;;
            if(!ch[u][c]) ch[u][c] = ++sz;
            u=ch[u][c];
        }
        val[u]=1<<(td++);
    }
};
int getFail(){
    queue<int>q; int u;
    f[0] = 0;
    for(int c=0;c<26;++c){
        u = ch[0][c];
        if(u)  { f[u]=0; q.push(u);}
    }
    while(!q.empty()){
        int r=q.front(); q.pop();
        for(int c=0;c<26;++c){
            u=ch[r][c];
            if(!u){
                ch[r][c]=ch[f[r]][c];
                continue;
            }
            q.push(u);
            f[u] = ch[f[r]][c];
            val[u]|=val[f[u]];
        }
    }
}
int num(int x){
    int ans = 0;
    while(x){
        if(x&1) ans++;
        x /= 2;
    }
    return ans;
}
char str[11];
int n,m,cnt;
int main(){
    while(~scanf("%d%d%d",&n,&m,&cnt)&&n) {
        Trie trie;    ans=0;
        for(int i=0;i<m;++i) {
            scanf("%s",str);
            trie.insert(str);
        }
        getFail();
        dp[0][0][0]=1;
        for(int i=0;i<n;++i)
            for(int j=0;j<=sz;++j)
                for(int k=0;k<(1<<m);++k)
                    if(dp[i][j][k])  for(int d=0;d<26;++d) {
                        int ret=ch[j][d];
                        dp[i+1][ret][k|val[ret]]=(dp[i+1][ret][k|val[ret]]+dp[i][j][k])%mod;
                    }
        for(int i=0;i<=sz;++i)
            for(int j=(1<<cnt)-1;j<(1<<m);++j)
                if(dp[n][i][j]&&num(j)>=cnt)
                    ans=(ans+dp[n][i][j])%mod;
        printf("%d\n",ans);
    }
}