A-串

题目链接：https://ac.nowcoder.com/acm/contest/9981/A

思路：
考虑是否可以由上一个状态再加一个字母得到当前状态：
dp[i]表示长度为i的字符串包含多少个us
1，dp[i]=dp[i-1]*26，相当于dp[i-1]表示长度为i-1包含us，再加上任意一个字母即为dp[i]状态的一部分
2，dp[i]另外的组成就是，由某个状态sta加上一个s构成。sta必须包含u，但是不能有子序列us，如果有子序列us则可能与1中情况冲突，所以sta状态为包含u但是不存在us子序列。
综上，dp[i]可以由加一个任意字母和加s来达到转移的过程。
关于状态sta的计算有两种思路如下：
思路1：直接数学计算sta状态：sta[i-1]=全部情况-不存在u情况-存在us子序列情况\(=26^{i-1}-25^{i-1}-dp[i-1]\)
则\(dp[i]=26\times dp[i-1]+26^{i-1}-25^{i-1}-dp[i-1]=26^{i-1}-25^{i-1}+25\times dp[i-1]\)
思路2：通过状态转换来得出sta状态(思路来着雨巨的视频讲解)
定义dp[i][0]为字符串长度为i的没有u的字符串种类数:则为i-1状态再加一个非u的字母
则\(dp[i][0]=dp[i-1][0]\times 25\)
定义dp[i][1]为字符串长度为i的有u无us的字符串种类数:则为i-1状态为加一个非s字母和i-1没有u的状态再加一个u两种状态转换过来
则\(dp[i][1]=dp[i-1][1]\times 25+dp[i-1][0]\)
定义dp[i][2]为字符串长度为i的有us的字符串种类数：则i状态为i-1状态加一个任意字母和i-1有u无us状态再加一个s两种状态转换过来
则\(dp[i][2]=dp[i-1][1]+dp[i-1][2]\times 26\)
收获：
计数类问题的解决方法一般为：\(\left\{\begin{aligned}1&，dp，由dp[i-1]\Rightarrow dp[i]\\2&，组合数计算\\3&，枚举，通过枚举小数据找规律\end{aligned}\right.\)
复习：
%：取模操作对 + * -没有影响，但是-的时候要 注意出现负数的情况可以通过取余后+M解决。（a/b）%M!=(a%M)/(b%M)

思路一代码:

#include<bits/stdc++.h>

using namespace std;
int num[(int)1e6+5];
int a[(int)1e6+5];
const int M=(int)1e9+7;
int main (){
    int n;
    cin>>n;
    a[1]=0;
    a[2]=1;
    int l=26,r=25;
    for(int i=2;i<=n-1;i++){
        l=(1LL*26*l)%M;
        r=(1LL*25*r)%M;
        num[i]=(M+l-r)%M;
    }
    for(int i=3;i<=n;i++){
        a[i]=(num[i-1]+1LL*25*a[i-1])%M;
    }
    int ans=0;
    for(int i=2;i<=n;i++){
        ans=(ans+a[i])%M;
    }
    cout<<ans;
    return 0;
}

思路二代码：

#include<iostream>

using namespace std;
const int M=(int)1e9+7;
int dp[(int)1e6+5][3];
int main (){
    int n;
    cin>>n;
    dp[2][0]=25*25;
    dp[2][1]=50;
    dp[2][2]=1;
    for(int i=3;i<=n;i++){
        dp[i][0]=1LL*25*dp[i-1][0]%M;
        dp[i][1]=(1LL*dp[i-1][1]*25%M+dp[i-1][0])%M;
        dp[i][2]=(dp[i-1][1]+1LL*dp[i-1][2]*26%M)%M;
    }
    int ans=0;
    for(int i=2;i<=n;i++)
        ans=(ans+dp[i][2])%M;
    cout<<ans;
    return 0;
}

A-串

原文：https://www.cnblogs.com/abestxun/p/14382207.html