制作ppt的软件免费/石家庄seo推广

没积分了。。更新一下。。

http://codeforces.com/contest/86/problem/C

AC自动机加DP经典题目，

题意：。。。

思路：构建AC自动机，在AC自动机上跑，这样通过构造可以保证满足条件。再次基础上DP计数，DP[?len ][ idx ][ fail ]

? ? ? ? ? len 表示 已经走了几步，idx表示在自动机上第几个节点，fail表示已经有几个字母没构成单词。

代码：

#include 
#define X first
#define Y second
#define MP make_pair
#define PB push_back
#define ll long long
#define pii pair
using namespace std;int n,m;
const int maxn=1005;
const ll mod=1e9+9;
string s;
ll dp[1005][105][15],vis[1005][105][15];//
int nxt[maxn][4],fail[maxn],len[maxn];
int cnt=0;
ll ans=0;
int rev[256];
ll mod_add(const ll &a,const ll &b){return (a+b)%mod;
}
void add(string s){int node=0;for(int i=0;i Q;for(int i=0;i<4;i++)if(nxt[0][i]!=0)Q.push(nxt[0][i]),fail[nxt[0][i]]=0;while(!Q.empty()){int T=Q.front();Q.pop();for(int i=0;i<4;i++){if(nxt[T][i]==0){nxt[T][i]=nxt[fail[T]][i];continue;}int u=nxt[T][i];fail[u]=nxt[fail[T]][i];len[u]=max(len[u],len[nxt[fail[T]][i]]);//????Q.push(u);}}
}
struct DP{int step,idx,wa;DP(int x=0,int y=0,int z=0){step=x,idx=y,wa=z;}
};
void get_ans(){queue Q;dp[0][0][0]=1;Q.push(DP(0,0,0));while(!Q.empty()){DP T=Q.front();Q.pop();for(int i=0;i<4;i++){int u=nxt[T.idx][i],f=T.wa+1;if(len[u]>=f) f=0;dp[T.step+1][u][f]=mod_add(dp[T.step+1][u][f],dp[T.step][T.idx][T.wa]);if(T.step+1>n>>m;for(int i=0;i>s,add(s);get_fail();get_ans();cout<