串

难度：4星

$dp[i][0]dp[i][0]$ 为前$ii$个字符中不包含字母 $uu$ 的情况数量。

$dp[i][1]dp[i][1]$为前i个字符中包含字母 $uu$ 且不包含 $usus$ 子序列的情况数量

$dp[i][2]dp[i][2]$为前i个字符中包含 $usus$ 子序列的情况数量。

由于字符串中 $uu$ 之前是否存在 $ss$ 对结果不产生影响，因此也可以直接不考虑前i个字符中是否包含 $ss$ 的情况。

可得转移方程：

$dp[i][0]=dp[i-1][0]\ast 25dp[i][0]\; =\; dp[i-1][0]*25$，即前 $i-1i-1$ 个字符不包含 $uu$ ，第 $ii$ 个字符可选择除 $uu$以外的所有字符。

$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]$，即前 $i-1i-1$ 个字符包含 $uu$ 时第 $ii$ 个字符可选择除 $ss$以外的所有字符，当前 $i-1i-1$ 个字符不包含 $uu$ 时可选择在第 $ii$ 个字符选择 $uu$ 。

$dp[i][2]=dp[i-1][2]\ast 26+dp[i-1][1]dp[i][2]\; =\; dp[i-1][2]*26+dp[i-1][1]$，即前 $i-1i-1$ 个字符包含 $usus$ 时第 $ii$ 个字符可选择任意字符,当前 $i-1i-1$ 个字符中包含 $uu$ 时，第 $ii$ 个字符可选择 $ss$ 。由于本题求长度不超过 $nn$ 的字符串，即将 ${\sum }_{i=1}^{n}dp[i][2]\backslash sum\_\{i=1\}^n\; dp[i][2]$ 输出即可

注意需对结果取模

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9+7;
ll n , dp[1100000][3];
int main() {
    scanf("%d",&n);
    dp[1][0] = 25;
    dp[1][1] = 1;
    dp[1][2] = 0;
    ll res = 0;
    for (int i = 2 ; i <= n ; i ++) {
        dp[i][0] = (dp[i-1][0]*25)%mod;
        dp[i][1] = ((dp[i-1][1]*25)%mod+dp[i-1][0])%mod;
        dp[i][2] = ((dp[i-1][2]*26)%mod+dp[i-1][1])%mod;
        res = (res+dp[i][2])%mod;
    }
    printf("%lld\n",res);
}