本文共 1440 字，大约阅读时间需要 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/