A 串
DP
链接：https://ac.nowcoder.com/acm/contest/9981/A
来源：牛客网

长度不超过nn、，且包含子序列“us”的、只由小写字母构成的字符串有多少个？ 答案对10^9+7取模。
所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。
例如，"unoacscc"包含子序列"us"，但"scscucu"则不包含子序列"us"
输入描述:
一个正整数n(2~1e6)
输出描述:
一个正整数，为满足条件的字符串数量对10^9 +7取模的值<

#include <bits/stdc++.h>
using namespace std;

const long long  N = 1e6+10;
const long long  mod = 1e9+7;
long long  n,m;
long long a1[N],a2[N],a3[N],a4[N];
//***a1,2,3,4分别存储字符串长度为i时没有U，有u没有us，含us，以及结果取模的值
int main(){
    cin >> n;
    a1[1] = 25 , a2[1] = 1, a3[1] =0;
    //a1[2] = 25*25,a2[2] = ,a3[2] = ;
    for(int i = 2 ; i <= n; i++){
        a3[i] = (a3[i-1]*26)%mod + a2[i-1];//
        a2[i] = (a2[i-1]*25)%mod + a1[i-1];//1
        a1[i] = (a1[i-1]*25)%mod;//1
        a4[0] +=a3[i];
        a1[i] %= mod;
        a2[i] %= mod;
        a3[i] %= mod;
        a4[0] %= mod;
    }
    cout << a4[0];
    return 0;
}