题解 [牛客练习赛60C] 操作集锦

• 操作集锦

题目描述

给定一个长度为 的有小写字母组成的字符串。

求长度为 的本质不同的子序列个数，对 取模。

正解

如果设 为考虑到第 个位置，且第 个位置必须选，选出的本质不同的子序列个数。

设出状态不难，难的是转移如何不会重复。

如果一个子序列只在出现的第一次被算入答案，就不会计算重复了对吧。

考虑构造出序列自动机（位置为 ，字符 的下一个位置），这是找子序列第一次出现的常见套路。

那么转移就很简单了，当前位置为 ，枚举当前长度为 ，转移字符为 ，则有 的转移。

最后所有 就是答案了。

#include <bits/stdc++.h>
#define N 1005

using namespace std;

const int mod = 1e9 + 7;

int n, K;
int nex[N][26], f[N][N];
char s[N];

int main() {
    scanf("%d %d", &n, &K);
    scanf("%s", s + 1);
    for(int c = 0; c < 26; ++c)
        nex[n][c] = n + 1;
    for(int c = 0; c < 26; ++c)
        for(int i = n - 1; i >= 0; --i)
            nex[i][c] = (s[i + 1] == 'a' + c ? i + 1 : nex[i + 1][c]); 
    f[0][0] = 1;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j <= n; ++j) {
            if(!f[i][j]) continue;
            for(int c = 0; c < 26; ++c)
                if(nex[i][c] <= n)
                    (f[nex[i][c]][j + 1] += f[i][j]) %= mod;
        }
    int ans = 0;
    for(int i = 0; i <= n; ++i)
        (ans += f[i][K]) %= mod;
    printf("%d\n", ans);
    return 0;
}