题意

给出长度为 的字符串，求长度为 的本质不同的子序列个数。

分析

设 表示前 个字母，长度为 的本质不同子序列个数。
考虑 来源。

  • 首先 可以来源于 ，也就是 不参与构成子序列
  • 然后考虑第 参与子序列，第一反应肯定是 。不过这会有重复。假设上一个相同字母的位置为 ，则 参与了两个相同子序列，所以要减掉这部分。

代码如下

#include <bits/stdc++.h>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define N 1005
using namespace __gnu_pbds;
using namespace std;
const int mod = 1e9 + 7;
typedef long long LL;
typedef unsigned long long uLL;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int ksm(int a, int b, int p){
    int s = 1;
    while(b){
        if(b & 1) s = z * s * a % p;
        a = z * a * a % p;
        b >>= 1;
    }
    return s;
}
int las[N], f[N][N], g[N];
char s[N];
int main(){
    int i, j, t, k, n, m;
    n = read(); k = read();
    scanf("%s", s + 1);
    for(i = 1; i <= n; i++){
        las[i] = g[s[i]];
        g[s[i]] = i;
    }
    for(i = 1; i <= n; i++){
        f[i][0] = 1;
        f[i][1] = f[i - 1][1] + (las[i] == 0);
    }
    for(i = 1; i <= n; i++){
        for(j = 2; j <= min(i, k); j++){
            f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % mod;
            if(las[i]) f[i][j] = (f[i][j] - f[las[i] - 1][j - 1]) % mod;
        }
    }
    printf("%d", (f[n][k] + mod) % mod);
    return 0;
}