网站做标签页,平面广告设计软件有哪些,小程序优点,公众号开发微商城题目链接#xff1a;hdu 6086 Rikka with String 题意#xff1a; 给你n个只含01的串#xff0c;和一个长度L,现在让你构造出满足s[i]≠s[|s|−i1] for all i∈[1,|s|] #xff0c;长度为2L#xff0c;并且包含给出的n个串#xff0c;问能有多少种这样的串。 题解#x…题目链接hdu 6086 Rikka with String 题意 给你n个只含01的串和一个长度L,现在让你构造出满足s[i]≠s[|s|−i1] for all i∈[1,|s|] 长度为2L并且包含给出的n个串问能有多少种这样的串。 题解 建立两个AC自动机一个用来放正串一个用来放反串。 由于题目有限制条件所以前L长度的字符一确定后L长度的字符就确定了。 所以考虑dp[i][j][k][u]表示长度为i第一个ac自动机走到了j这个节点第二个ac自动机走到了k这个节点当前包含子串的状态为u。 第一维可以滚动数组。 然后这样dp完后只能找到包含的串要么在左边L里要么在右边L里对于跨越分界线的串还没有算进去。 然后我们在将第L长度的dp状态进行暴力枚举将j,k节点所代表的前缀拿来合并进行对给出的串暴力匹配一下。 然后就可以算到全部的情况了。 1 #includebits/stdc.h2 #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_N2007,tyn2;7 int t,n,L,P998244353;8 char s[8][30],pre[200][30],suf[200][30];9 int dp[2][130][130][16];10 11 inline void up(int a,int b){a(ab)%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 x0){19 for(int lenstrlen(s),i0,w;ilen;xtr[x][w],i)20 if(!tr[x][wgetid(s[i])])21 {22 nw(),tr[x][w]tot;23 strcpy(p[tot],p[x]);24 int Lenstrlen(p[x]);25 p[tot][Len]w0;26 p[tot][Len1]0;27 }28 cnt[x]1(idx-1);29 }30 void build(int head1,int tail0){31 for(int i0;ityn;i)if(tr[0][i])Q[tail]tr[0][i];32 while(headtail)for(int xQ[head],i0;ityn;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 now0;45 mst(dp[now],0),dp[now][0][0][0]1;46 int U(1n)-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 nxA.tr[j][0],nx2B.tr[k][1];54 up(dp[now][nx][nx2][u|A.cnt[nx]|B.cnt[nx2]],dp[now^1][j][k][u]);55 nxA.tr[j][1],nx2B.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,tpstrlen(tp));66 strcat(tmp,tp);67 int ttp0;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 ans0;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,tmpstrlen(tmp));96 B.insert(tmp,i,suf);97 }98 A.build(),B.build();99 solve();
100 }
101 return 0;
102 } View Code 转载于:https://www.cnblogs.com/bin-gege/p/7325505.html
