Skip to content

1025 Keep at Most 100 Characters

Statement

Metadata

  • 作者: CAO, Peng
  • 单位: Google
  • 代码长度限制: 16 KB
  • 时间限制: 150 ms
  • 内存限制: 64 MB

Given a string which contains only lower case letters, how many different non-empty strings you can get if you can keep AT MOST 100 characters in the original order? (Note: The string obtained is a "sub-sequence" of the original string.)

Input Specification

Each input file contains one test case, which is only one line containing the string whose length is no larger than 1000.

Output Specification

Output the number of different non-empty strings if you can only keep at most 100 characters. Since the answer might be super large, you only need to output the answer modulo 1000000007.

Sample Input 

aabac

Sample Output 

19

Hint

The strings are:

a, b, c, aa, ab, ac, ba, bc, aab, aaa, aac, aba, abc, bac, aaba, aabc, abac, aaac, and aabac.

Tutorial

思路：

f_{i, j} 表示前 i 个字符，保留 j 个字符所形成的sub-sequence数量。

转移有：

f_{i, j} = f_{i - 1, j} + f_{i - 1, j - 1}

但是这样会有重复，我们考虑当前字符 i，它前一次出现的位置是 k，那么 f_{k - 1, j - 1} 的贡献是重复的。

简单来说，就是保留当前字符，并且在 [1, k - 1] 的位置中任取 j - 1 个字符的贡献，被算了两遍。

Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int mod = 1e9 + 7;
constexpr int N = 1e3 + 10;
inline void chadd(int &x, int y) {
    x += y;
    if (x >= mod)
        x -= mod;
}
int n, pre[330];
int f[N][N];
char s[N];

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    memset(f, 0, sizeof f);
    memset(pre, -1, sizeof pre);
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        int ch = s[i] - 'a';
        for (int j = 0; j < i; ++j) {
            if (pre[ch] == -1) {
                chadd(f[i][j + 1], (f[i - 1][j + 1] + f[i - 1][j]) % mod);
                //  if (j == 0) chadd(f[i][j + 1], 1);
            } else {
                chadd(f[i][j + 1], (1ll * f[i - 1][j + 1] + f[i - 1][j] - f[pre[ch] - 1][j] + mod) % mod);
            }
        }
        f[i][0] = 1;
        //  if (pre[ch] == -1) chadd(f[i][1], 1);
        pre[ch] = i;
    }
    int res = 0;
    for (int i = 1; i <= 100; ++i) chadd(res, f[n][i]);
    printf("%d\n", res);
    return 0;
}
Last update: May 4, 2022
Back to top