HDU2825 Wireless Password AC自动机+状压dp

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int P=20090717;
#define debug(x) cout<<#x<<"="<<x<<endl
#define bug(x) cout<<#x<<"="<<x<<" "
struct node{
	int to[26],g,d;
}tr[505];
char str[15];
int n,m,K,que[505],allc;
inline void Insert(int len,int id){
	int rt=1;
	for(int i=0;i<len;++i){
		if(!tr[rt].to[str[i]])tr[rt].to[str[i]]=++allc;
		rt=tr[rt].to[str[i]];
	}
	tr[rt].d|=1<<id-1;
}
inline void build(){
	int l=0,r=0;
	for(que[r++]=1;l<r;){
		int u=que[l++];
		for(int i=0,j,s;i<26;++i){
			for(j=tr[u].g;j;j=tr[j].g)
				if(tr[j].to[i])break;
			if(s=tr[u].to[i]){
				tr[s].g=j?tr[j].to[i]:1;
				tr[s].d|=tr[tr[s].g].d;
				que[r++]=s;
			}
			else tr[u].to[i]=j?tr[j].to[i]:1;
		}
	}
}
inline void clear(){
	for(int i=1;i<=allc;++i)
		for(int j=tr[i].g=tr[i].d=0;j<26;++j)
			tr[i].to[j]=0;
	allc=1;
}
int dp[2][1<<11][505],cnt_bit[1<<11];
inline void Mod_add(int &a,int b){
	if((a+=b)>=P)a-=P;
}
inline void Mod_sub(int &a,int b){
	if((a-=b)<0)a+=P;
}
inline int Mod(int x){
	if(x>=P)return x-P;
	if(x<0)return x+P;
	return x;
}
inline void gao(){
	clear();
	for(int i=1;i<=m;++i){
		scanf("%s",str);
		int len=strlen(str);
		for(int j=0;j<len;++j)
			str[j]-='a';
		Insert(len,i);
	}
	build();
	int cur=0,nxt=1;
	memset(dp,0,sizeof(dp));
	dp[nxt][0][1]=1;
	for(int i=1;i<=n;++i){
		swap(cur,nxt);
		//Init
		for(int j=0;j<1<<m;++j)
			for(int k=1;k<=allc;++k)
				dp[nxt][j][k]=0;
		for(int j=0;j<1<<m;++j)
			for(int k=1;k<=allc;++k){
				if(!dp[cur][j][k])continue;
				for(int l=0;l<26;++l)
					Mod_add(dp[nxt][j|tr[tr[k].to[l]].d][tr[k].to[l]],dp[cur][j][k]);
			}
	}
	int res=0;
	for(int j=0;j<1<<m;++j){
		if(cnt_bit[j]<K)continue;
		for(int k=1;k<=allc;++k)
			if(~dp[nxt][j][k])Mod_add(res,dp[nxt][j][k]);
	}
	cout<<res<<endl;
}
inline void Init(){
	for(int i=1;i<1<<10;++i)
		cnt_bit[i]=cnt_bit[i^(i&-i)]+1;
}
int main(){
	for(Init();cin>>n>>m>>K,n|m|K;)gao();
	return 0;
}