本文共 1472 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要计算长度为 k 的操作视频的数量，其中每个操作视频由原序列的子序列组合而成，并且每个操作视频的本质不同。操作视频的本质不同意味着每个操作符号的组合是唯一的。

方法思路

我们可以使用动态规划来解决这个问题。定义 dp[j][c] 表示长度为 j 以字符 c 结尾的操作符号的数量。这里，j 的范围是从 1 到 k，c 的范围是从 0 到 25（对应于字母 a 到 z）。

解决代码

#include 
   
    
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1005;
ll dp[MAXN][26];
char s[MAXN];
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    scanf("%s", s + 1);
    if (k == 0) {
        puts("1");
        return 0;
    }
    for (int i = 1; i <= n; ++i) {
        if (i > k) break;
        int current_char = s[i] - 'a';
        for (int j = k; j >= 2; --j) {
            ll sum = 0;
            for (int x = 0; x < 26; ++x) {
                sum += dp[j-1][x];
                if (sum >= MOD) sum -= MOD;
            }
            dp[j][current_char] = (dp[j][current_char] + sum) % MOD;
        }
        dp[1][current_char] = 1;
    }
    ll ans = 0;
    for (int c = 0; c < 26; ++c) {
        ans = (ans + dp[k][c]) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}
   

代码解释

该方法通过动态规划有效地统计了所有可能的操作符号组合，确保了时间复杂度为 O(nk)。

转载地址：http://xhewz.baihongyu.com/