传送门
翻译：输入正整数(n)和(k(1 leqslant n leqslant 400, 1 leqslant k leqslant 10))，求长度为(n)的01串中有多少个不含长度至少为(k)的回文连续子串。比如(n=k=3)时只有4个串满足条件：001, 011, 100, 110。
这题的关键在于：如果字符串中不含有长度为(k)的回文串，那么也一定不含有长度大于(k)的回文串。因为长度大于(k)的回文串，会在检查他的子串时就被筛去了。
看到(k)很小，想到状压dp，令(dp[i][S])表示长度为(i)的字符串中，后(k+1)位的字符串是(S)时的合法的字符串个数。
为什么是(k+1)位，因为奇偶回文串的关系，长度为(k)的回文串只能筛掉长度为(k+2，k+4 ldots)的回文串。
首先预处理出来长度为(k+1)的合法串，即不含有长度为(k)或(k+1)的回文子串的01串。
然后就可以dp了：对于当前第(i)位，枚举后(k+1)位状态，再枚举第(i+1)位是0还是1，然后拼成新的(k+1)位，转移到(i+1)。
最后的答案就是(sum dp[n][S])。
代码里把(K > n)和(K=n)的情况特判了一下，写的可能有点啰嗦。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 405;
const int maxs = 2050;
const ll mod = 1e9 + 7;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
}
int n, m, K;
ll dp[maxn][maxs];
bool v[maxs];
In bool judge(int x, int len)
{
bool flg1 = 0, flg2 = 0, flg3 = 0;
for(int i = 0, j = len - 1; i < j; ++i, --j)
if(((x >> i) & 1) ^ ((x >> j) & 1)) flg1 = 1;
for(int i = 0, j = len - 2; i < j; ++i, --j)
if(((x >> i) & 1) ^ ((x >> j) & 1)) flg2 = 1;
for(int i = 1, j = len - 1; i < j; ++i, --j)
if(((x >> i) & 1) ^ ((x >> j) & 1)) flg3 = 1;
return (flg1 && flg2 && flg3);
}
In void init()
{
Mem(dp, 0);
m = 1 << (K + 1);
for(int i = 0; i < m; ++i) v[i] = judge(i, K + 1);
}
In int ADD(ll a, ll b) {return a + b < mod ? a + b : a + b - mod;}
In void solve()
{
for(int i = 0; i < m; ++i) dp[K + 1][i] = v[i];
for(int i = K + 2; i <= n; ++i)
for(int j = 0; j < m; ++j)
{
int tp = (j << 1) & (m - 1);
if(v[tp]) dp[i][tp] = ADD(dp[i][tp], dp[i - 1][j]);
if(v[tp | 1]) dp[i][tp | 1] = ADD(dp[i][tp | 1], dp[i - 1][j]);
}
ll ans = 0;
for(int i = 0; i < m; ++i) ans = ADD(ans, dp[n][i]);
write(ans), enter;
}
In ll quickpow(ll a, ll b)
{
ll ret = 1;
for(; b; b >>= 1, a = a * a % mod)
if(b & 1) ret = ret * a % mod;
return ret;
}
In int work0()
{
ll ret = 0;
for(int i = 0; i < (1 << K); ++i)
{
bool flg = 0;
for(int j = 0, k = n - 1; j < k && !flg; ++j, --k)
if(((i >> j) & 1) ^ ((i >> k) & 1)) flg = 1;
ret += flg;
}
return ret;
}
int main()
{
// MYFILE();
int T = read();
while(T--)
{
n = read(), K = read();
if(K > n) write(quickpow(2, n)), enter;
else if(K == n) write(work0()), enter;
else init(), solve();
}
return 0;
}