串(dp)

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

长度不超过$n$，且包含子序列us的、只由小写字符构成的字符串有多少个？答案对$10^9+7$取模。

所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。

例如，"unoacscc"包含子序列"us"，但"scscucu"则不包含子序列"us"

输入描述:

一个正整数$n(2 <= n <= 10^6)$

输出描述:

一个正整数，为满足条件的字符串数量对$10^9+7$取模的值

示例1

输入

复制

$2$

输出

复制

$1$

说明

仅有“us”这一个字符串合法

示例2

输入

复制

$3$

输出

复制

$77$

说明

长度为3的字符串里，

形状是"u?s"的共有26个

形状是"?us"的共有26个

形状是"us?"的共有26个。

但是,"uss"和"uus"被各多计算了1次，应该减去，

所以共有26*3-2=76个。

再加上长度为2的"us"，所以长度不超过3的合法字符串共有77个。

示例3

输入

复制

$874520$

输出

复制

$16471619$

看到n的范围跟结果大小, 确定是dp, 可惜我dp太弱了, 一直不知道该如何下手, 直到昨天学了一下递归改dp的思路, 才感觉茅塞顿开.
思路如下,先写出暴力的递归函数:

 1 ll ans;
 2 void dfs(int cur, bool u, bool s)
 3 {
 4     ans += u && s;
 5     if (cur == n)
 6         return;
 7     for(int i = 0; i < 26; ++ i){
 8         dfs(cur + 1, u || 'a' + i == 'u', u && (s || 'a' + i == 's'));
 9     }
10 }

暴力思路

显然对$2 <= n <= 1e6$的范围来说这个算法会超时, 可以从参数里面发现, 这三个状态都是我们要转移的状态.

所以可以确定我们要改的dp数组中有三个状态, 即$dp[n][u][s]$, n为字符串长度, u跟s表示当前字符串中是否包括了u或者s字符

首先我们根据题目可以知道, 长度为1的时候是不可能包含字符串"us"的, 但可以包含一个字符, 其中有1个字符'u'和其他25个字符.

所以我们可以得知$dp[1][1][0] = 1$( 长度为1的字符串中包含字符'u'的情况只有一种), $dp[1][0][0] = 25$ (长度为1的字符串中不包含u的情况, 即有25种不同的字符, 所以这里的值是25)

之后就是如何通过初始状态转移了.

在包含字符'u'跟字符's'的字符串中, 字符's'出现的位置一定要在字符'u'出现的位置之后, 这是题目中描述的有效的字符串的要求.

我们可以知道, 在字符串后面加上一个字符, 有三种情况,

在不含字符'u'跟字符's'的字符串中, 在末尾添加一个字符'u', 总共有$dp[n - 1][0][0]$种情况, 状态转移到$dp[n][1][0]$上; 在末尾添加除'u'以外的字符, 总共有$25 * dp[n - 1][0][0]$种情况, 状态转移到$dp[n][0][0]$上.
在包含字符'u'但不包含字符's'的字符串中, 添加一个字符's', 总共有$dp[n - 1][1][0]$种情况, 状态转移到$dp[n][1][1]$上; 在末尾添加除's'以外的字符, 总共有$25 * dp[n - 1][1][0]$种情况, 状态转移到$dp[n][1][0]$上.
在包含字符'u'且包含字符's'的字符串中, 添加任意字符, 都将转移到$dp[n][1][1]$上, 总共有$26 * dp[n - 1][1][1]$种情况.

所以我们可以从中总结出状态转移方程

$dp[n][1][1] = dp[n][1][0] + 26 * dp[n][1][1]$

$dp[n][1][0] = dp[n][0][0] + 25 * dp[n][1][0]$

$dp[n][0][0] = 25 * dp[n][0][0]$

至此, 我们可以根据上述状态转移方程轻松写出代码.

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 #include <string>
 5 using namespace std;
 6 typedef long long ll;
 7 constexpr int mod = 1e9 + 7;
 8 
 9 constexpr int MAXN = 1e6 + 7;
10 int n;
11 ll dp[MAXN][2][2]; //下标表示长度, dp[n]表示长度为n的字符串中带us的字符串有多少个
12 
13 ll ans;
14 int main()
15 {
16     ll ans = 0;
17     dp[1][0][0] = 25;
18     dp[1][1][0] = 1;
19     // dp[2] = 1;
20     cin >> n;
21     // dfs(0, false, false);
22     for (int i = 2; i <= n; ++i)
23     {
24 
25         dp[i][1][1] = (dp[i - 1][1][0] + 26 * dp[i - 1][1][1] % mod) % mod;
26         ans = (ans + dp[i][1][1]) % mod;
27         dp[i][1][0] = (dp[i - 1][0][0] + 25 * dp[i - 1][1][0] % mod) % mod;
28         dp[i][0][0] = dp[i - 1][0][0] * 25 % mod;
29     }
30     cout << ans << endl;
31     return 0;
32 }

AC代码