題目鏈接：hdu 6086 Rikka with String

題意：

給你n個只含01的串，和一個長度L,現(xiàn)在讓你構(gòu)造出滿足s[i]≠s[|s|?i+1] for all i∈[1,|s|]?，長度為2L，并且包含給出的n個串，問能有多少種這樣的串。

題解：

建立兩個AC自動機，一個用來放正串，一個用來放反串。

由于題目有限制條件，所以前L長度的字符一確定，后L長度的字符就確定了。

所以考慮dp[i][j][k][u]，表示長度為i，第一個ac自動機走到了j這個節(jié)點，第二個ac自動機走到了k這個節(jié)點，當(dāng)前包含子串的狀態(tài)為u。

第一維可以滾動數(shù)組。

然后這樣dp完后，只能找到包含的串要么在左邊L里要么在右邊L里，對于跨越分界線的串，還沒有算進(jìn)去。

然后我們在將第L長度的dp狀態(tài)進(jìn)行暴力枚舉，將j,k節(jié)點所代表的前綴拿來合并，進(jìn)行對給出的串暴力匹配一下。

然后就可以算到全部的情況了。

1 #include<bits/stdc++.h> 2 #define mst(a,b) memset(a,b,sizeof(a)) 3 #define F(i,a,b) for(int i=(a);i<=(b);++i) 4 using namespace std; 5 6 const int AC_N=200+7,tyn=2; 7 int t,n,L,P=998244353; 8 char s[8][30],pre[200][30],suf[200][30]; 9 int dp[2][130][130][1<<6]; 10 11 inline void up(int &a,int b){a=(a+b)%P;} 12 13 struct AC_automation{ 14 int tr[AC_N][tyn],cnt[AC_N],Q[AC_N],fail[AC_N],tot; 15 inline int getid(char x){return x-'0';} 16 void nw(){cnt[++tot]=0,fail[tot]=0;mst(tr[tot],0);} 17 void init(){tot=-1,fail[0]=-1,nw();} 18 void insert(char *s,int idx,char p[][30],int x=0){ 19 for(int len=strlen(s),i=0,w;i<len;x=tr[x][w],i++) 20 if(!tr[x][w=getid(s[i])]) 21 { 22 nw(),tr[x][w]=tot; 23 strcpy(p[tot],p[x]); 24 int Len=strlen(p[x]); 25 p[tot][Len]=w+'0'; 26 p[tot][Len+1]=0; 27 } 28 cnt[x]=1<<(idx-1); 29 } 30 void build(int head=1,int tail=0){ 31 for(int i=0;i<tyn;i++)if(tr[0][i])Q[++tail]=tr[0][i]; 32 while(head<=tail)for(int x=Q[head++],i=0;i<tyn;i++) 33 if(tr[x][i]) 34 { 35 fail[tr[x][i]]=tr[fail[x]][i],Q[++tail]=tr[x][i]; 36 cnt[tr[x][i]]|=cnt[tr[fail[x]][i]]; 37 } 38 else tr[x][i]=tr[fail[x]][i]; 39 } 40 }A,B; 41 42 void solve() 43 { 44 int now=0; 45 mst(dp[now],0),dp[now][0][0][0]=1; 46 int U=(1<<n)-1; 47 F(i,1,L) 48 { 49 now^=1,mst(dp[now],0); 50 F(j,0,A.tot)F(k,0,B.tot)F(u,0,U) 51 if(dp[now^1][j][k][u]) 52 { 53 int nx=A.tr[j][0],nx2=B.tr[k][1]; 54 up(dp[now][nx][nx2][u|A.cnt[nx]|B.cnt[nx2]],dp[now^1][j][k][u]); 55 nx=A.tr[j][1],nx2=B.tr[k][0]; 56 up(dp[now][nx][nx2][u|A.cnt[nx]|B.cnt[nx2]],dp[now^1][j][k][u]); 57 } 58 } 59 char tmp[300],tp[40]; 60 F(i,1,A.tot)F(j,1,B.tot)F(u,0,U-1) 61 if(dp[now][i][j][u]) 62 { 63 strcpy(tmp,pre[i]); 64 strcpy(tp,suf[j]); 65 reverse(tp,tp+strlen(tp)); 66 strcat(tmp,tp); 67 int ttp=0; 68 F(ii,1,n) 69 { 70 if(strstr(tmp,s[ii])!=0) 71 ttp|=(1<<(ii-1)); 72 } 73 if((u|ttp)==U) 74 up(dp[now][i][j][U],dp[now][i][j][u]); 75 } 76 int ans=0; 77 F(i,0,A.tot)F(j,0,B.tot)if(dp[now][i][j][U]) 78 up(ans,dp[now][i][j][U]); 79 printf("%d\n",ans); 80 } 81 82 int main() 83 { 84 scanf("%d",&t); 85 while(t--) 86 { 87 A.init(),B.init(); 88 scanf("%d%d",&n,&L); 89 F(i,1,n) 90 { 91 scanf("%s",s[i]); 92 A.insert(s[i],i,pre); 93 char tmp[30]; 94 strcpy(tmp,s[i]); 95 reverse(tmp,tmp+strlen(tmp)); 96 B.insert(tmp,i,suf); 97 } 98 A.build(),B.build(); 99 solve(); 100 } 101 return 0; 102 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/bin-gege/p/7325505.html

總結(jié)

以上是生活随笔為你收集整理的hdu 6086 Rikka with String(AC自动机+状压dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。