[DP][状压DP] UVa 1633 Dyslexic Gollum

自己想的时候一直在纠结的问题是怎么保存(第k个之前的是不是0/1)的问题，纠结了很久没有get到正点上，因为单单这样的话似乎会导致状态信息不足。。会漏掉一些情况。看了绿书题解，一看到状压顿时明白了。。。k最大只有10，这样的话只要把构造串的最后k位01情况压缩起来就可以了。另外一个问题就是这样的话会不会导致有中间产生长度超过k的回文串，答案是否定的，因为回文串本身其实有着子结构的性质，如果以某个节点为最后一位的长度k的回文串没有被构造出来，那么一定不会有更长的回文串包含这个点的。

#include

using namespace std;
const int maxn=4e2+5;
const int mod=1e9+7;
typedef long long LL;


LL add(LL a,LL b)
{
    return a+b>mod?a+b-mod:a+b;
}

LL dp[maxn][1051];
bool isp[1050],isp2[1050];

void init(int k)
{
    //memset(isp,0,sizeof(isp));
    for(int i=0;i<=1024;i++)
    {
        int flag=1;
        for(int j=0;2*j<=(k-1);j++)
        {
            if((1&(i>>j))!=(1&(i>>(k-1-j)) ))
            {
                flag=0;
                break;
            }
        }
        isp[i]=flag;
    }
    k--;
    for(int i=0;i<=1024;i++)
    {
        int flag=1;
        for(int j=0;2*j<=(k-1);j++)
        {
            if((1&(i>>j))!=(1&(i>>(k-1-j)) ))
            {
                flag=0;
                break;
            }
        }
        isp2[i]=flag;
    }
}

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int t;
    int n,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        if(n>1];
                        if(!isp2[b>>1]||i==k)
                            dp[i][b]=add(dp[i][b],dp[i-1][(1<<(k-1))|(b>>1)]);
                    }
                    else
                    {
                        dp[i][b]=dp[i-1][(1<<(k-1))|(b>>1)];
                        if(!isp2[b>>1]||i==k)
                            dp[i][b]=add(dp[i][b],dp[i-1][b>>1]);
                    }
                    //cout<>1]<