牛客 DP61 串

长度不超过nn，且包含子序列“us”的、只由小写字母构成的字符串有多少个？ 答案对10^9+710
9 +7取模。
所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。
例如，“unoacscc"包含子序列"us”，但"scscucu"则不包含子序列"us"

输入描述： 一个正整数n
输出描述： 一个正整数，为满足条件的字符串数量对10^9+7取模的值

此题只要能够写出状态转移方程就比较好写了
如果没有及时取余的话会导致超时
所以要在每次迭代的时候就及时做取余 *** 作
状态中有三个参数：
f [ n ] = [ d p 1 , d p 2 , d p 3 ] f[n] = [dp_1,dp_2,dp_3] f[n]=[dp1​,dp2​,dp3​]

• d p 1 dp_1 dp1​表示n位数字时，完全不含有u和s的字符串个数
• d p 2 dp_2 dp2​表示n位数字时，含有u但是不含有前u后s的字符串个数
• d p 3 dp_3 dp3​表示n位数字时，已经含有前u后s的字符串个数

转移公式如下表示：
d p 3 = d p 2 + d p 3 ∗ 26 dp_3 = dp_2 + dp_3*26 dp3​=dp2​+dp3​∗26
d p 2 = d p 1 ∗ 25 + d p 2 dp_2 = dp_1*25 + dp_2 dp2​=dp1​∗25+dp2​
d p 1 = d p 1 ∗ 25 dp_1 = dp_1*25 dp1​=dp1​∗25

用时和内存都排名很前面：

n = int(input())
def dfs(n):
    if n == 2:return 1
    dp = [25,1,0]#无u,有u无us，有us
    result = 0
    mod = 10**9+7
    for i in range(2,n+1):
        dp[2] = (dp[1]+dp[2]*26)%mod
        dp[1] = (dp[0]+dp[1]*25)%mod
        dp[0] = (dp[0]*25)%mod 
        result += dp[2]
    return result%mod
print(dfs(n))