涉及知识点：DP
题面
有一个长度为 \(n\ (\leq 6000)\) 字符串 \(s\)，可以执行如下操作：选定一个 \(i\in[1,n]\)，将 \(i\) 左侧或者右侧的连续若干个字符变成 \(s[i]\)（选定的字符要连续且有一个与 \(i\) 相邻）。你可以执行任意次这样的操作，请问最后可以得到多少种本质不同的合法的字符串？定义一个字符串是合法的，当且仅当这个字符串不存在长度超过 \(k\) 的由同一种字符构成的子串。
思路
题面所述的操作可以进行无限次，并且后面的操作又可以覆盖前面操作的结果（比如说aaba \(\rightarrow\)aaab），总而言之，这么难以处理的操作提示着我们这道题不应该从操作本身出发，而应该去寻找操作之后的序列有什么性质，而经过思考后我们发现，由于操作的本质是从一个点进行拓展，即使有字符可能被完全覆写，但是剩下字符间的相对顺序是不变的，一个字符不可能在不完全覆写它旁边字符的情况下拓展到更远的地方，因此当我们把操作后的序列相邻的相同字符合并后，我们可以说合并后的序列一定是原序列的子序列。
现在问题就变得不那么棘手了一些，我们需要在原长为 \(n\) 的序列中找到所有长度为 \(m\) 的相邻字符不同的子序列，对于每个子序列，我们求出它可以“还原”成多少种操作后的序列，而这个数量并不难统计，用组合意义思考，实际上就是：将长度为 \(n\) 的序列划分为 \(m\) 个长度不超过 \(k\) 的子段的方案数。
现在目标很明确了，我们要干两件事，考虑 DP 转移：
-
求原序列有多少长度为 \(m\) 的相邻字符不同的子序列
\(f[i][j]\) 表示长度为 \(i\)，最后一个字符是 \(j\) 的方案数，\(s[i]\) 表示长度为 \(i\) 的子序列数
\(f[i][j]=s[i-1]-f[i-1][j]\)
\(s[i]=f[i][0]+f[i][1]+\cdots+f[i][MAXC]\)
-
求长度为 \(n\) 的序列划分为 \(m\) 个长度不超过 \(k\) 的子段的方案数
\(f[i][j]\) 表示长度为 \(i\) 划分为 \(j\) 个长度不超过 \(k\) 的子段的方案数
\(f[i][j]=f[i-1][j-1]+f[i-2][j-1]+\dots+f[i-k+1][j-1]\)
这里再加上一个前缀和优化，为了方便编码，代码中的 \(i\) 和 \(j\) 是反过来的
最后对应长度相乘再累加统计答案即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL P=1e9+7;
const int MAXN=6005;
int n,k,a[MAXN],f[MAXN][MAXN],pre[MAXN][MAXN],sum[MAXN];
LL ans=0;
string s;
int main(){
freopen("aqours.in","r",stdin);
freopen("aqours.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k>>s;s=" "+s;
for(int i=1;i<=n;i++)
if(isalpha(s[i])) a[i]=s[i]-'a'+1;
else a[i]=0;
sum[0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
sum[j]=(1LL*sum[j]-f[j][a[i]]+P)%P;
f[j][a[i]]=(1LL*sum[j-1]-f[j-1][a[i]]+P)%P;
sum[j]=(1LL*sum[j]+f[j][a[i]])%P;
}
}
memset(f,0,sizeof(f));
f[0][0]=1;
for(int i=0;i<=n;i++) pre[0][i]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=((1LL*f[i][j]+pre[i-1][j-1])%P-(j-k-1<0 ? 0 : pre[i-1][j-k-1])+P)%P;
pre[i][j]=(1LL*pre[i][j-1]+f[i][j])%P;
}
}
for(int i=1;i<=n;i++){
ans=(ans+1LL*f[i][n]*sum[i]%P)%P;
}
cout<<ans<<endl;
return 0;
}