题目的主要信息：

• 长度不超过$nn$，且包含子序列“us”的、只由小写字母构成的字符串有多少个
• 答案对$10^9+710^9+7$取模
• 子序列指必须u在s前，中间可以有间隔

具体做法：

我们可以对这个分情况讨论：

• $dp[i][0]dp[i][0]$表示字符串长度为$ii$，但是字符串中没有u的情况有多少种，初始为$dp[1][0]=25dp[1][0]=25$

• $dp[i][1]dp[i][1]$表示字符串长度为$ii$，但是字符串中有u没有s的情况，初始为$dp[1][1]=1dp[1][1]=1$

• $dp[i][2]dp[i][2]$表示字符串长度为$ii$，字符串中有us的情况，初始为$dp[1][2]=0dp[1][2]=0$

我们可以遍历每个长度，找到每个长度的$dp[i][2]dp[i][2]$，将结果累加取模就是我们的结果。而长度每增加1，我们如下讨论：

• 第一种情况没有u只能由前一个长度的第一种情况而来，增加1个字符，可以增加25种情况，于是有$dp[i][0]=dp[i-1][0]\ast 25dp[i][0]\; =\; dp[i\; -\; 1][0]\; *\; 25$

• 第二种情况有u但没有s可以由前一个长度的第一种情况增加1个u的字母而来，或者由前一个长度的第二种情况，增加一个非s的字母而来，这里非s就有25中可能性，于是有$dp[i][1]=dp[i-1][1]\ast 25+dp[i-1][0]dp[i][1]\; =\; dp[i\; -\; 1][1]\; *\; 25\; +\; dp[i\; -\; 1][0]$

• 第三种情况us刚好都有，可以前一个长度的第三种情况增加一个任意字母而来，这里有26种情况，或者由前一个长度的第二种情况增加一个字母s而来，于是有$dp[i][2]=dp[i-1][1]+dp[i-1][2]\ast 26dp[i][2]\; =\; dp[i\; -\; 1][1]\; +\; dp[i\; -\; 1][2]\; *\; 26$

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n;
    int mod = 1e9 + 7;
    cin >> n;
    long long count = 0;
    vector<vector<long long> > dp(n + 1, vector<long long>(3, 0));
    dp[1][0] = 25; //字符串长度为1，没有u
    dp[1][1] = 1; //字符串长度为1，有u，没有s
    dp[1][2] = 0; //字符串长度为1，有us
    for(int i = 2; i <= n; i++){ //遍历所有可能的长度状态转移
        dp[i][0] = (dp[i - 1][0] * 25) % mod;
        dp[i][1] = (dp[i - 1][1] * 25 + dp[i - 1][0]) % mod;
        dp[i][2] = (dp[i - 1][1] + dp[i - 1][2] * 26) % mod;
        count = (count + dp[i][2]) % mod; //各个长度累加和取模
    }
    cout << count << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历2到$nn$
• 空间复杂度：$O(n)O(n)$，$3\ast n3*n$的dp数组大小