串

解法一：
设dp[i]表示长度为i的合法字符串
dp[i]的状态转移有两种
一：长度为i-1的合法的字符串数量
在这种情况中第i位随便填一个字母就可以了即26dp[i-1]
二：长度为 i-1的包含u但不包含us的字符串的数量
这种情况中的 i位必须要写 s那么怎样计算第二种情况的字符串的数量呢？
这样算：长度为 i-1的所有字符串的数量-其中不包含u的字符串-包含us的
也就是26^(i-1)-25^(i-1)-dp[i-1]
那么dp[i]=26^(i-1)-25^(i-1)+25dp[i-1]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
const int maxn=1e6+10;
const int p=1e9+7;
ll dp[maxn];
ll ans;
ll quick_pow(ll x,ll y){
    ll res=1;
    while(y){
        if(y&1){
            res=res*x%p;
        }
        x=x*x%p;
        y>>=1;
    }    
    return res;
}
int main(){
    cin>>n;

    for(int i=2;i<=n;i++){
        dp[i]=(quick_pow(26,i-1)-quick_pow(25,i-1)+25*dp[i-1]+p)%p;
        ans=(ans+dp[i])%p;
    }
    cout<<ans<<endl;
    return 0;
}

解法二：
设dp[i][0/1/2]
dp[i][0]表示前i位中没有u的
dp[i][1]表示前i位中有u没s的
dp[i][2]表示前i位中包含us的

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
const int maxn=1e6+10;
const int p=1e9+7;
ll dp[maxn][3];
ll ans;
int main(){
    cin>>n;
     dp[1][0]=25;//no u
     dp[1][1]=1;//have u no s
     dp[1][2]=0;// have us
    for(int i=2;i<=n;i++){
        dp[i][0]=25*dp[i-1][0]%p;
        dp[i][1]=(25*dp[i-1][1]+dp[i-1][0])%p;
        dp[i][2]=(26*dp[i-1][2]+dp[i-1][1])%p;
        ans=(ans+dp[i][2])%p;
    }
    cout<<ans;
    return 0;
}