<span>HDU - 2825 Wireless Password （AC自动机+状压DP）</span>
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=2825
题意：给一些字符串，构造出长度为n的字符串，它至少包含k个所给字符串，求能构造出的个数。
题解：
对end[]节点标记数组进行改动,用二进制下第几位表示即为包含第几个给定子串；
状态转移方程为：dp[i+1][x][k|end[x]]=(dp[i+1][x][k|end[x]]+dp[i][j][k])%mod；(没懂为什么要用‘ | ’ ，等搞明白了在更新吧，，)
dp[i][j][l] 表示长度 i 在第j个结点且当前包含字符串集合为 l 的方案数；
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 const ll mod=20090717; 6 const ll maxn = 111; 7 ll ans=0; 8 ll sum[1100]; 9 ll n,m,k; 10 11 struct tire{ 12 ll nxt[maxn][30],fail[maxn],end[maxn],tot,root,vis[maxn]; 13 ll newNode(){ 14 for(ll i=0;i<26;i++) nxt[tot][i] = -1; 15 end[tot++] = 0; 16 return tot-1; 17 } 18 void Init(){ 19 tot = 0; 20 root = newNode(); 21 memset(dp,0,sizeof(dp)); 22 } 23 void Insert(char *buf,ll id){ 24 ll len = strlen(buf),i,u = root; 25 for(i=0;i<len;i++){ 26 ll x = buf[i]-'a'; 27 if(nxt[u][x]==-1) nxt[u][x] = newNode(); 28 u = nxt[u][x]; 29 } 30 end[u] |= 1<<id; 31 } 32 void build(){ 33 queue <ll> q; 34 fail[root] = root; 35 for(ll i=0;i<26;i++){ 36 if(nxt[root][i]==-1) nxt[root][i] = root; 37 else{ 38 fail[nxt[root][i]] = root; 39 q.push(nxt[root][i]); 40 } 41 } 42 while(!q.empty()){ 43 ll now = q.front(); 44 q.pop(); 45 for(ll i=0;i<26;i++){ 46 if(nxt[now][i]==-1) nxt[now][i] = nxt[fail[now]][i]; 47 else{ 48 fail[nxt[now][i]] = nxt[fail[now]][i]; 49 q.push(nxt[now][i]); 50 } 51 } 52 end[now]|=end[fail[now]]; 53 } 54 } 55 ll dp[30][111][1<<10]; 56 void solve(){ 57 dp[0][0][0]=1; 58 for(ll i=0;i<n;i++){ 59 for(ll j=0;j<tot;j++){ 60 for(ll k=0;k<(1<<m);k++){ 61 if(dp[i][j][k]){ 62 for(ll u=0;u<26;u++){ 63 ll x=nxt[j][u]; 64 dp[i+1][x][k|end[x]]+=dp[i][j][k]; 65 dp[i+1][x][k|end[x]]%=mod; 66 } 67 } 68 } 69 } 70 } 71 ans=0; 72 for(ll i=0;i<tot;i++){ 73 for(ll j=0;j<(1<<m);j++){ 74 if(dp[n][i][j]&&sum[j]>=k) ans=(ans+dp[n][i][j])%mod; 75 } 76 } 77 cout<<ans<<endl; 78 } 79 }ac; 80 81 char s1[maxn]; 82 83 int main() 84 { 85 for(ll i=0;i<(1<<10);i++){ 86 for(ll j=0;j<10;j++){ 87 if(i&(1<<j)) sum[i]++; 88 } 89 } 90 while(cin>>n>>m>>k){ 91 if(!n&&!m&&!k) break; 92 ac.Init(); 93 for(ll i=0;i<m;i++){ 94 cin>>s1; 95 ac.Insert(s1,i); 96 } 97 ac.build(); 98 ac.solve(); 99 } 100 return 0; 101 }
