题目链接
这个题一开始想不会写，因为不含长度至少为 k k k的回文连续子串是一个比较模糊的概念，后来去参考这个博客，思路逐渐清晰
证明部分
所有大于等于 k k k的回文子串一定包含一个长度为小于 k k k的回文子串：
当 k k k为奇数的时候，要凑成长度为 k k k的回文串需要一个前缀为 k − 2 k-2 k−2的奇数个数回文串，例如 1010 , k = 5 1010,k=5 1010,k=5，含有的回文子串为 010 010 010，最后加上 1 1 1即可构成长度为k的回文串；或者一个长度为 k − 1 k−1 k−1的偶数回文串两边各匹配一个相同的值来凑成，例如 10000 , k = 5 10000,k=5 10000,k=5，最后加上 1 1 1即可得到长度为 6 6 6的回文串，这时候长度就是 k + 1 k+1 k+1。当 k k k为偶数的时候，跟奇数的情况刚好相反，所以得证
那么我们不难知道 k + 2 , k + 3... k+2,k+3... k+2,k+3...都无需再枚举，因为他们都含有长度为 k k k或者 k + 1 k+1 k+1的子串，只要我们在长度为 k k k和 k + 1 k+1 k+1时结束字符串，那么就没有后顾之忧了
DP部分
首先预处理出长度 12 12 12之内的所有字符串， v i s [ i ] [ j ] vis[i][j] vis[i][j]表示长度为 i i i，对应十进制数大小为 j j j的字符串是否为回文字符串，使用位运算判断即可
设 d [ i ] [ j ] d[i][j] d[i][j]表示考虑第i位，对应十进制数为j的字符串的合法个数，因为我们最多只需考虑最后 k + 1 k+1 k+1位。我们尝试由已知合法状态更新未知状态， f k fk fk为尝试在 j j j后添加一位 0 0 0或者 1 1 1之后的最后 k k k位，那么有：
d [ i ] [ f k ] = ( d [ i ] [ f k ] + d [ i − 1 ] [ j ] ) % M o d , v i s [ k ] [ f k ] & & v i s [ k + 1 ] [ ( j < < 1 ) ∣ h ] d[i][fk]=(d[i][fk]+d[i-1][j])\%Mod,vis[k][fk] ~\&\&~ vis[k+1][(j<<1)|h] d[i][fk]=(d[i][fk]+d[i−1][j])%Mod,vis[k][fk] && vis[k+1][(j<<1)∣h]
#include <set> #include <map> #include <stack> #include <queue> #include <math.h> #include <cstdio> #include <string> #include <bitset> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define lowbit(x) (x&(-x)) #define mkp(x,y) make_pair(x,y) #define mem(a,x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> P; const double eps=1e-8; const double pi=acos(-1.0); const int inf=0x3f3f3f3f; const ll INF=1e18; const int Mod=1e9+7; const int maxn=2e5+10; ll d[405][1<<12]; bool vis[15][1<<12]; int cal(int x,int i){ return (x&(1<<i))>>i; } bool check(int n,int x){ for(int i=0;i<n/2;i++) if(cal(x,i)!=cal(x,n-1-i)) return 0; return 1; } void init(){ for(int i=1;i<=12;i++) for(int j=0;j<(1<<i);j++) vis[i][j]=check(i,j); } int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int t,n,k; init(); cin>>t; while(t--){ cin>>n>>k; if(k==1){ cout<<"0"<<endl; continue; } memset(d,0,sizeof d); d[0][0]=1; for(int i=1;i<=n;i++) for(int j=0;j<(1<<min(i,k));j++) if(d[i-1][j]) for(int h=0;h<2;h++){ //枚举新添加一位可能的状态 int fk=((j<<1)|h)&((1<<k)-1); //取得最后k位 if(i>=k && vis[k][fk]) continue; if(i>k && vis[k+1][(j<<1)|h]) continue; d[i][fk]=(d[i][fk]+d[i-1][j])%Mod; } int ans=0; for(int i=0;i<(1<<k);i++) ans=(ans+d[n][i])%Mod; cout<<ans<<endl; } return 0; }