牛客练习赛60 操作集锦

题解： 通俗易懂的官方题解。
$f\left[i\right]\left[j\right]$f[i][j]表示前 $i$i个字符中长度为 $j$j的子序列的个数。
不考虑重复子序列的情况下的状态转移方程：
$f\left[i\right]\left[j\right]=f[i-1]\left[j\right]+f[i-1][j-1]$f[i][j]=f[i−1][j]+f[i−1][j−1]，即不取第 $i$i个字符和取第 $i$i个字符两种情况。

根据题意：重复的子序列应该是由在 $i$i之前的且与 $s\left[i\right]$s[i]相同的字符产生的，根据状态转移方程，考虑 $pre\left[s\right[i\left]\right]$pre[s[i]]为 $s\left[i\right]$s[i]这个字符在 $i$i之前离 $i$i最近的位置，那么 $f\left[pre\right[s\left[i\right]\left]\right]\left[j\right]$f[pre[s[i]]][j]对重复子序列做出的贡献是取了 $pre\left[s\right[i\left]\right]$pre[s[i]]这个位置，那么需要减去的重复子序列就是这部分即 $f\left[pre\right[s\left[i\right]]-1]\left[j\right]$f[pre[s[i]]−1][j]。
那么最终的转移方程就是： $f\left[i\right]\left[j\right]=f[i-1]\left[j\right]+f[i-1][j-1]-f\left[pre\right[s\left[i\right]]-1]\left[j\right]$f[i][j]=f[i−1][j]+f[i−1][j−1]−f[pre[s[i]]−1][j]

状态初始化即 $f\left[i\right]\left[0\right]=1$f[i][0]=1，对于任意前 $i$i个字符，一个也不选也是一种合法方案。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll; 
const int N = 1010;
const ll mod = 1e9 + 7;
char s[N];
ll f[N][N];
int n, k, pre[26];

int main()
{
	scanf("%d%d%s", &n, &k, s + 1);
	
	for(int i = 0; i <= n; i++) f[i][0] = 1; //前i个字符中一个都不选也是一种合法方案 
	for(int i = 1; i <= n; i++) {
		int id = s[i] - 'a';
		for(int j = 1; j <= i; j++) {
			f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
			if(pre[id]) f[i][j] -= f[pre[id] - 1][j - 1];
			f[i][j] = (f[i][j] % mod + mod) % mod;
		}
		pre[s[i] - 'a'] = i;
	}
	
	printf("%lld\n", f[n][k]);
}