先看两道题
题目一：zbw的签到
题目描述
一个合法的字符串定义为
- 由小写字母组成
- 包含子序列"cn"
问长度在 $n(n \le 3e5)$ 以内的合法字符串的数量
问在所有字符串 $t$ 中，子序列"abc"出现的次数之和
二者区别在于一个字符串对于答案来说，能为题目一至多带来1的贡献，而对题目二能带来不止1的贡献。
并且题目一是无限制条件的全随机，题目二是有限制条件(非'?'固定)的伪随机。
而且发现题目一似乎与组合数学有关，毕竟全部字符未知，所有状态就是 $26^n$ 种，取其中合法的状态。
但是题目二从所有状态下手会很头疼，因为次数和字符串状态牵涉太深，更像是动态规划，讨论字符的取值对总答案的贡献。
在此贴一个题目一的题解：
枚举从 $1-n$ 的长度 $len$，对于 $len$ 考虑从后往前搜索第 $i$ 位的取值
设置 $dfs(pos, ok1, ok2)$ 表示为搜索到第 $pos$ 位，之前状态为 $ok1, ok2$ 的所有合法序列
- $ok1$ 代表 是否出现 "n"
- $ok2$ 代表 是否出现 “cn”
对 $dfs$ 分类讨论：
- $ok2 = 1$, 那么前 $pos$ 位任意取，共有 $26^{pos}$ 种
- $pos == 0$,搜索结束，返回 $ok2$ 的取值
- 否则，结果未知，只能继续枚举 第 $pos$ 位的取值 $dfs(pos - 1, ok1 \lor s_{pos} == \text{'n'}, ok2 \lor (ok1 \land s_{pos} == \text{'c'}))$
观察 $pos-1$ 得到搜索会重复，并且对于每一位 $pos$, 只有 $2^2$ 种可能，可以记忆化来优化时间
代码
typedef long long ll;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n;
ll dp[N][2][2];
ll qmi(ll a, ll b){
ll res = 1;
while (b){
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
ll dfs(int pos, int ok1, int ok2){
if (dp[pos][ok1][ok2] != -1){
return dp[pos][ok1][ok2];
}
if (ok2){
return dp[pos][ok1][ok2] = qmi(26, pos);
}
if (pos == 0){ //结尾
return ok2;
}
ll res = 0;
for (int i = 0; i < 2; i ++ ){ // 'n' 'cn'
res += dfs(pos - 1, ok1 | (i == 0), ok2 | (ok1 & i == 1));
}
res += 24 * dfs(pos - 1, ok1, ok2) % mod;
res %= mod;
return dp[pos][ok1][ok2] = res;
}
void solve() {
cin >> n;
ll ans = 0;
memset(dp, -1, sizeof dp);
for (int i = 1; i <= n; i ++ ){
ans = (ans + dfs(i, 0, 0)) % mod;
}
cout << ans << '\n';
}