题解 UVA1633 【禁止的回文子串 Dyslexic Gollum】

对于任意一个长度k大于等于2的01串，它不是回文串当且仅当“掐头去尾”得到的长度为k-2的01串不是回文串。 那么，对于题中这个长度为n的串，只需要保证里面不含长度为k或者k+1的回文子串。 所以，在状压dp时，定义now为当前正准备填01但还没填的位，只需记录now之前紧挨着的长度为k的子串state，状态转移的时候判断当前位的数字接到state之后新形成的长度为k和k+1的子串是否合法即可。 dfs预处理出长度为k和k+1回文串，按照长度分别存到mark[]和mark1[]里面；每次在state的末尾添加新的01时，将state左移一位再或上0或者1得到长度为k+1的新子串，再按位与上(1<<k)-1得到长度为k的子串，判断是否为回文串。 第一次写题解，如果有需要改进的地方恳请您指出orz ```cpp #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <cstdlib> #define rep(i,a,b) for(register int i=a;i<=b;i++) #define per(i,b,a) for(register int i=b;i>=a;i--) using namespace std; void qr(int &x) { x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); } const int mod=1e9+7,maxn=514; int n,k,f[maxn][2100],mrk[2100],mrk1[2100]; int dp(int now,int state)//结尾为now-1的长度k子串为state { int &ans=f[now][state]; if(ans!=-1)return ans; if(now==n+1)return ans=1; ans=0; rep(nx,(state<<1),((state<<1)|1)) if(mrk1[nx]&&mrk[((1<<k)-1)&nx]) ans+=dp(now+1,(((1<<k)-1)&nx)),ans%=mod; return ans; } void search(int now,int state) { if(now==k) mrk[state]=0; else if(now==k+1) mrk1[state]=0; else search(now+2,(state<<1)+(1<<(now+1))+1),search(now+2,state<<1); } void solve() { if(n<k) { printf("%d\n",1<<n); return; } memset(mrk,1,sizeof(mrk)),memset(mrk1,1,sizeof(mrk1)),memset(f,-1,sizeof(f)); search(1,1),search(1,0),search(0,0); int ans=0; rep(i,0,(1<<k)-1)if(mrk[i])ans+=dp(k+1,i),ans%=mod; printf("%d\n",ans); } int main() { int T;qr(T); rep(i,1,T) { qr(n),qr(k); solve(); } return 0; } ```