题面
题解
可以发现，(S) 和 (T) 相似，等价于它们的最长公共子序列长度至少为 (n - k)。
首先考虑如何求出两个字符串的 ( ext{LCS})（最长公共子序列）。考虑 dp：
设 (f_{i,j}) 表示 (S[1sim i]) 与 (T[1sim j]) 的 ( ext{LCS}) 长度，转移是显然的：
然后考虑如何拓展到 (T) 任意的情况。自然的想法是 dp 套 dp：
设 (dp[j][f_{1,j},f_{2,j},cdots,f_{n,j}]) 表示只考虑 (T) 的前 (j) 位，那么这 (j) 位有多少种选取方式，使此时的 (f_{*,j}) 数组如 dp 下标所示。
这个状态设计显然是可以优化的，不难证得 (f_{i+1,j}-f_{i,j}in{0,1})，又由于 (f_{0,j}=0)，所以我们把 (dp) 数组的第二维变成差分数组 (c_i=f_{i+1}-f_{i,j}) 的 01 串状压即可。
考虑这个 dp 的时间复杂度，状态数是 (O(n2^n)) 的。直接暴力 DP 的时间复杂度就约为 (O(2^noperatorname{poly}(n)))。考虑如何利用 (k) 很小这个性质进行优化。
首先考虑优化状态数。
考虑某个满足 (|i-j|>k) 的 (f_{i,j})（显然有 (f_{i,j}leq min(i,j))），再考虑这个 (f_{i,j}) 转移到 (f_{n,n}) 时最大会变成多少：观察最上面给出的 (f_{i,j}) 递推式，显然按第一种情况转移值才会变大，而第一种情况最多转移 (min(n-i,n-j)) 次，所以从 (f_{i,j}) 转移到 (f_{n,n}) 时的值不大于：
所以这个 (f_{i,j}) 不可能使 (f_{n,n}geq n-k)。
于是，与其记录整个 (f) 数组，我们只需要记录 (f_{j−k,j} , f_{j−k+1,j},cdots, f_{j+k,j})，这可以通过一个长度为 (2k) 的差分数组以及一个 (f_{j,j}) 得到。（这个差分数组也可以用 01 串状压表示）
又由于 (f_{j,j}) 的值必须介于 ([j − k, j]) 之间才能使 (f_{n,n}geq n-k)，所以我们将 (dp) 数组的第二维换成一个数 (xin [0,k]) 表示 (f_{j,j}=j-k+x)，第三维换成差分数组的 01 串状压。此时 (dp) 的总状态数只有 (O(nk2^{2k}))。
再考虑优化转移。
转移的过程是这样的：对于 (dp[j][x][sta])，枚举一个字符 (c) 为 (T[j+1])，向 (dp[j+1][x'][sta']) 转移。（其中 (x') 和 (sta') 需要我们计算出来）
为了方便转移，我们可以先预处理一个 pair 数组 (turn[j][x][sta][match])，表示当 (dp[j][x][sta]) 向 (dp[j+1][x'][sta']) 转移，枚举的字符 (c) 和 (S[j-k+1],S[j-k+2],cdots,S[j+k+1]) 的匹配状态为 (match) 时，(x') 和 (sta') 分别是多少。
也就是说，我们知道了 (f_{j-ksim j+k,j}) 和 (match)，要求此时的 (f_{j-k+1sim j+k+1,j+1})。
按照最上面的递推式正常转移即可。
然后你会发现一个很神奇的东西：要求出 (x) 和 (sta) 的变化量根本不需要 (j)，只需要 (x) 和 (sta)！
所以 (turn) 的第一维 (j) 可以直接去掉。
所以才叫预处理 turn。
注意 (match) 也是可以预处理的，然后此时预处理的时间是 (O(k^22^{2k}2^{2k+1}+26nk)=O(k^22^{4k+1}+26nk))，可以接受。
转移的时间优化到了 (O(26nk2^{2k}))。
其实已经能跑过了，但有点卡。
所以可以进一步的优化：
你发现对于枚举的 (c)，只要 (c) 不在 (S[j-k+1],S[j-k+2],cdots,S[j+k+1]) 内出现过，(match) 就等于 (0)，也就是说它们都相等，此时得到的 (x') 和 (sta') 都是相同的。
所以说，假设 (S[j-k+1],S[j-k+2],cdots,S[j+k+1]) 中有 (num) 种字符，那么我们一次算出 (match=0) 时的 (x') 和 (sta')，然后转移 (dp[j+1][x'][sta']gets dp[j+1][x'][sta']+(26-num)dp[j][x][sta]) 即可。
易知 (numleq 2k+2leq 9)，所以这部分我们枚举 (c) 用 (turn) 数组转移即可。
转移的时间复杂度降低到了约 (O(10nk2^{2k}))。
然后能 1s AC 了。（时限 2s）
#include<bits/stdc++.h>
#define K 5
#define N 30010
#define mod 998244353
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
namespace modular
{
inline int add(int x,int y){if((x+=y)>=mod)x-=mod; return x;}
inline int dec(int x,int y){if((x-=y)<0)x+=mod; return x;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
}
using namespace modular;
struct data
{
int x,sta;
}turn[K][260][520];
int n,k,s[N];
int match[N][26];
int dp[N][K][260];
int f[K<<1],g[K<<1];
char ss[N];
bool vis[30];
int main(){
scanf("%s%d",ss+1,&k);
n=strlen(ss+1);
for(int i=1;i<=n;i++) s[i]=ss[i]-'A';
int pow2k=(1<<(k<<1)),pow2k1=pow2k<<1;
for(int i=1;i<=n;i++)
{
for(int c=0;c<26;c++)
{
int sta=0;
for(int l=i+k;l>=i-k;l--)
{
if(l<1||l>n) sta<<=1;
else sta=sta<<1|(c==s[l]);
}
match[i][c]=sta;
}
}
for(int x=0;x<=k;x++)
{
for(int sta=0;sta<pow2k;sta++)
{
f[k]=x;
for(int i=k+1;i<=2*k;i++) f[i]=f[i-1]+((sta>>(i-1))&1);
for(int i=k-1;i>=0;i--) f[i]=f[i+1]-((sta>>i)&1);
for(int mat=0;mat<pow2k1;mat++)
{
for(int i=1;i<=2*k+1;i++)
{
if((mat>>(i-1))&1) g[i]=f[i-1]+1;
else g[i]=max(g[i-1],f[i]);
}
turn[x][sta][mat].x=g[k+1]-1;
int nsta=0;
for(int i=2*k;i>=1;i--) nsta=nsta<<1|(g[i+1]-g[i]);
turn[x][sta][mat].sta=nsta;
}
}
}
dp[0][k][0]=1;
for(int i=0;i<n;i++)
{
for(int x=0;x<=k;x++)
{
for(int sta=0;sta<pow2k;sta++)
{
if(!dp[i][x][sta]) continue;
int num=0;
for(int j=max(1,i+1-k);j<=min(n,i+1+k);j++)
{
if(!vis[s[j]]) num++;
vis[s[j]]=1;
}
int nx=turn[x][sta][0].x,nsta=turn[x][sta][0].sta;
if(nx>=0) dp[i+1][nx][nsta]=add(dp[i+1][nx][nsta],mul(26-num,dp[i][x][sta]));
for(int j=max(1,i+1-k);j<=min(n,i+1+k);j++)
{
if(!vis[s[j]]) continue;
vis[s[j]]=0;
nx=turn[x][sta][match[i+1][s[j]]].x,nsta=turn[x][sta][match[i+1][s[j]]].sta;
if(nx>=0) dp[i+1][nx][nsta]=add(dp[i+1][nx][nsta],dp[i][x][sta]);
}
}
}
}
int ans=0;
for(int x=0;x<=k;x++)
for(int sta=0;sta<pow2k;sta++)
ans=add(ans,dp[n][x][sta]);
printf("%d
",ans);
return 0;
}
/*
GUGUA
1
*/