首页 > 代码库 > bzoj 3768: spoj 4660 Binary palindrome二进制回文串
bzoj 3768: spoj 4660 Binary palindrome二进制回文串
Description
给定k个长度不超过L的01串，求有多少长度为n的01串S满足：
1.该串是回文串
2.该串不存在两个不重叠的子串，在给定的k个串中。
即不存在a<=b<c<=d，S[a,b]是k个串中的一个，S[c,d]是k个串中的一个
(It does not contain two non-overlapped substrings in the given list of K binary strings.)
举个例子，若给定2(k=2)个01串：101和1001
1010001和1010101均不满足条件。前者不满足条件1，后者不满足条件2
Input
第一行两个整数n,k
以下k行，每行一个01串
Output
输出一个整数表示答案，答案mod 1000000007（10^9+7）
对原串和反串分别建ac自动机，从两边向中间处理回文串，同时在自动机上走，若匹配到一个串就记录并回到起点
dp状态表示为 当前已确定前缀、后缀在ac自动机上的位置，以及是否已匹配到一个串 的方案数
最后检查是否在跨过中点的位置匹配到一个串
#include<cstdio>#include<cstring>#include<algorithm>const int P=1e9+7;int n,k,ls[33];char s[33][33];inline void inc(int&a,int b){ b+=a-P; a=b+(b>>31&P);}struct acam{ int ch[907][2],fa[907]; int S[907][33]; bool e[907]; int ptr; acam(){ memset(this,0,sizeof(acam)); ptr=1; ch[0][0]=ch[0][1]=1; } void ins(char*s,int a){ int w=1; for(int i=0;s[i];++i){ int c=s[i]-‘0‘,&u=ch[w][c]; if(!u)u=++ptr; w=u; S[w][a]|=1<<i; } e[w]=1; } void ins(char*s,int a,int len){ int w=1; for(int i=len-1;i>=0;--i){ int c=s[i]-‘0‘,&u=ch[w][c]; if(!u)u=++ptr; w=u; S[w][a]|=1<<i; } e[w]=1; } void build(){ int q[907],ql=0,qr=0; q[++qr]=1; while(ql!=qr){ int w=q[++ql]; for(int i=0;i<2;++i){ int&u=ch[w][i]; (u?fa[q[++qr]=u]:u)=ch[fa[w]][i]; } } for(int i=2;i<=qr;++i){ int w=q[i],f=fa[w]; e[w]|=e[f]; for(int j=0;j<k;++j)S[w][j]|=S[f][j]; } }}t1,t2;int f[2][907][907][2];int main(){ scanf("%d%d",&n,&k); for(int i=0;i<k;++i){ scanf("%s",s[i]); ls[i]=strlen(s[i]); t1.ins(s[i],i); t2.ins(s[i],i,ls[i]); } t1.build(); t2.build(); int now=0; f[0][1][1][0]=1; for(int t=0;t<n/2;++t,now^=1){ memset(f[now^1],0,sizeof(f[0][0])*(t1.ptr+2)); for(int c=0;c<2;++c){ for(int a=1;a<=t1.ptr;++a)if(!t1.e[a]){ int a1=t1.ch[a][c],is=0; if(t1.e[a1])a1=1,is=1; int(*f1a)[2]=f[now^1][a1]; int(*f0a)[2]=f[now][a]; for(int b=1;b<=t2.ptr;++b)if(!t2.e[b]){ int b1=t2.ch[b][c]; int v=is; if(t2.e[b1])b1=1,++v; for(int x=0;x+v<2;++x){ inc(f1a[b1][x+v],f0a[b][x]); } } } } } if(n&1){ memset(f[now^1],0,sizeof(f[0][0])*(t1.ptr+2)); for(int c=0;c<2;++c){ for(int a=1;a<=t1.ptr;++a)if(!t1.e[a]){ int a1=t1.ch[a][c],is=0; if(t1.e[a1])a1=1,is=1; int(*f1a)[2]=f[now^1][a1]; int(*f0a)[2]=f[now][a]; for(int b=1;b<=t2.ptr;++b)if(!t2.e[b]){ int v=is; for(int x=0;x+v<2;++x){ inc(f1a[b][x+v],f0a[b][x]); } } } } now^=1; } int ans=0; for(int a=1;a<=t1.ptr;++a){ for(int b=1;b<=t2.ptr;++b){ inc(ans,f[now][a][b][0]); for(int c=0;c<k;++c)if(t1.S[a][c]<<1&t2.S[b][c])goto o; inc(ans,f[now][a][b][1]); o:; } } printf("%d\n",ans); return 0;}
bzoj 3768: spoj 4660 Binary palindrome二进制回文串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。