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

2020-10-16 16:35:02


对于任意一个长度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

#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;
}