链接：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;
}
