描述

问有多少字符串满足以下条件：

• 长度不超过$nn$
• 包含子序列us 结果对$1e9+71e9+7$取模

思路

• 典型的dp问题，设$dp[n][0]dp[n][0]$表示长度为$nn$且不包含字母u的字符串数目，$dp[n][1]dp[n][1]$表示长度为$nn$字母u的字符串数目，$dp[n][2]dp[n][2]$表示长度为$nn$且包含子序列us的数目，答案为${\sum }_{i\le n}dp[i][2]\backslash sum\_\{i\; \backslash leq\; n\}dp[i][2]$
• 转移方程为$\{\begin{array}{c}dp[n][2]=dp[n-1][1]+26\ast dp[n-1][2]\\ dp[n][1]=dp[n-1][0]+25\ast dp[n-1][1]\\ dp[n][0]=25\ast dp[n][0]\end{array}\backslash begin\{cases\}dp[n][2]=dp[n-1][1]+26*dp[n-1][2]\; \backslash \backslash dp[n][1]=dp[n-1][0]+25*dp[n-1][1]\backslash \backslash dp[n][0]=25*dp[n][0]\backslash end\{cases\}$
• 由于$dpdp$状态转移仅和前一个状态相关，可以采取边遍历边$dpdp$的方法省略一维度，具体实现见代码

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
int dp[3]; //0->空，1->包含u，2->包含us
int main()
{
    int n;
    int ans=0;
    scanf("%d",&n);
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        dp[2]=(1LL*dp[1]+26LL*dp[2])%MOD;
        dp[1]=(1LL*dp[0]+25LL*dp[1])%MOD;
        dp[0]=25LL*dp[0]%MOD;
        ans=(1LL*ans+dp[2])%MOD;
    }
    printf("%lld\n",ans);
}

时间复杂度$O(n)O(n)$，空间复杂度$O(1)O(1)$