串

链接：https://ac.nowcoder.com/acm/contest/9981/A

题目描述

长度不超过n，且包含子序列“us”的、只由小写字母构成的字符串有多少个？ 答案对1e9+7取模。
所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。
例如，”unoacscc”包含子序列”us”，但”scscucu”则不包含子序列”us”

思路

用递推的方法,通过在已有字符串的末端增加字符,从而逐步得到答案

f[i][0]表是长度为i的不含u的合法字符串数量

f[i][1]表示含u但是不含us的

f[i][2]表示含us的

那么可以得到

f[i][0]=f[i-1][0]*25,即在末尾加上一个除了u之外的字符

f[i][1]=f[i-1][1]*25(含有u了,那么加一个除了s之外的字符)+f[i-1][0] (在末尾加上u)

f[i][2]=f[i-1][2]*26(含有us了,那么随便加一个字符)+f[i-1][1] (前面有u无s,那么在末尾加上s)

代码

#include <cstdio>
#include <iostream>
using namespace std;
#define ll long long

const int maxn = 1e6 + 7;
const ll mod = 1e9 + 7;

int n;
ll f[maxn][3], ans;

int main()
{
    scanf("%d", &n);
    f[1][0] = 25;
    f[1][1] = 1;
    f[1][2] = 0;
    for(int i = 2; i <= n; ++i) {
        f[i][0] = f[i-1][0] * 25 % mod;
        f[i][1] = (f[i-1][1]*25 % mod + f[i-1][0]) % mod;
        f[i][2] = (f[i-1][2]*26 % mod + f[i-1][1]) % mod;
        ans = (ans + f[i][2]) % mod;//注意题目要求是”不超过n“
    }
    printf("%lld\n", ans);
    return 0;
}