CCPC 2021 Online - F 复盘：固定模式子序列 DP 与贡献划分

发表于 分类于
将芳香子序列按 nunhehheh 的最后一个 h 分类，用固定模式串子序列 DP 统计前缀方案，再乘上后缀 a 的非空选择数。重点复盘累计状态与当前位置新增状态的区别。

题目与计数对象

CCPC 2021 Online F - Nun Heh Heh Aaaaaaaaaaa

给定若干个只包含小写英文字母的字符串。对于每个字符串，需要统计其中有多少个子序列形如：

1
nunhehheh + 至少一个 a

子序列只要求所选下标严格递增，不要求字符连续。即使最后得到的字符串相同，只要选择的下标不同，也要分别计数。答案对 998244353998244353 取模。

题目给出的范围是：测试组数 T≤1000T\le 1000，单个字符串长度不超过 10510^5，所有字符串的总长度不超过 10610^6。

这是一道固定模式串的子序列计数 DP。代码本身不长，真正值得复盘的是如何划分方案，以及如何区分累计状态和当前位置新增的状态。

按最后一个 h 划分方案

一个合法子序列由两部分组成：

1
nunhehheh

以及它后面非空的一串 a。

假设 nunhehheh 的最后一个 h 选在位置 ii，并且 ii 后面共有 cic_i 个 a。后缀中的每个 a 都可以选或不选，因此共有 2ci2^{c_i} 个子集；排除一个都不选的情况，非空选择数就是：

2ci−1 2^{c_i}-1

再记 fif_i 为在 ii 之前选出 nunhehhe 的方案数。固定 ii 作为最后一个 h 时，产生的完整方案数为：

fi(2ci−1) f_i\left(2^{c_i}-1\right)

于是总答案可以写成：

∑si=hfi(2ci−1) \sum_{s_i=\texttt{h}} f_i\left(2^{c_i}-1\right)

这种划分不会重复。任意一个合法子序列中，nunhehheh 都有唯一的最后一个 h，所以它只会被归入一个位置 ii；反过来，前八个字符的选法、固定的第九个 h 和后缀 a 的非空选法拼起来，也一定得到一个合法子序列。

只维护前八个字符

完整固定前缀是 nunhehheh，但最后一个 h 已经被用来划分答案，因此 DP 只需要维护它前面的八个字符：

1
nunhehhe

设这个长度为 88 的模式串为 PP。扫描原字符串的一个前缀时，定义：

Dj=从已经扫描的字符中选出 P 的前 j 个字符的方案数 D_j=\text{从已经扫描的字符中选出 }P\text{ 的前 }j\text{ 个字符的方案数}

其中 0≤j≤80\le j\le 8。特别地，D0=1D_0=1，因为空串只有一种选法：什么都不选。其余状态初始化为 00。实现时，DjD_j 存在 dp[j] 中。

扫描到字符 sis_i 时，如果它等于 PP 的第 jj 个字符，就可以把它接到所有已经匹配前 j−1j-1 个字符的方案后面：

Dj←Dj+Dj−1 D_j\leftarrow D_j+D_{j-1}

对应的一维转移是：

1
2
3
4
5
for (int j = 8; j >= 1; --j) {
    if (s[i] == temp[j - 1]) {
        dp[j] = (dp[j] + dp[j - 1]) % mod;
    }
}

这里必须倒序更新。假设模式串是 nn，如果正序计算，那么扫描一个 n 时会先用它更新 D1D_1，紧接着又用刚更新的 D1D_1 更新 D2D_2，相当于同一个原串位置被选了两次。倒序时，右侧状态读取的仍然是加入当前字符之前的左侧状态，每个位置至多使用一次。

当当前字符是 h 时，更新前的 D8D_8 就是前面定义的 fif_i。从语义上看，可以先累加这个位置的答案贡献，再进行 DP 转移。AC 代码采用了相反的书写顺序，但当前字符 h 不会更新以 e 结尾的 D8D_8，所以两种顺序在这里等价。

后缀 a 的非空选择

为了得到每个位置右侧有多少个 a，从后往前预处理后缀计数：

cnti=cnti+1+[si=a] cnt_i=cnt_{i+1}+[s_i=\texttt{a}]

实现中，这个量存放在数组 a 中。只有当 sis_i 是 h 时才会计算贡献，所以 a[i] 虽然定义为从 ii 开始的 a 数量，但它与从 i+1i+1 开始的数量相同。

当前位置的贡献就是：

1
dp[8] * (qpow(2, a[i]) - 1)

当后面没有 a 时，括号内等于 00，这个 h 不会产生合法方案。快速幂的返回值在 [1,mod−1][1,mod-1] 内，而这里减一不会出现负数；两个取模后的因子相乘也不会超过 long long 的范围。

初版思路为什么重复计数

我最初维护了完整模式串的状态：

D9=截至当前位置选出 nunhehheh 的累计方案数 D_9=\text{截至当前位置选出 }\texttt{nunhehheh}\text{ 的累计方案数}

然后在每个 h 处尝试计算：

1
dp[9] * 2^cntA - 1

这里有两个相互独立的问题。

第一个问题是把累计完成量当成了当前位置的新完成量。D9D_9 会保留此前所有已经完成的 nunhehheh，后面每遇到一个 h，旧方案仍然在这个状态中。如果每次都把整个 D9D_9 加入答案，旧方案就会反复贡献。

例如：

1
nunhehhehha

两个连续的 h 都可以作为固定前缀的最后一个字符，因此正确答案是 22。若先更新完整状态、再在每个 h 处使用累计的 D9D_9，两次贡献分别包含 11 个和 22 个完整前缀，最终会得到 33。多出来的那一次，就是第一个 h 结束的旧方案在第二个 h 处又被计算了一遍。

正确的统计粒度应当是：只保留前八个字符的累计方案数，再固定当前 h 作为第九个字符。这样 D8D_8 与当前位置一一配合，得到的正是“以当前位置新完成”的方案。

第二个问题是减一的位置。假设固定最后一个 h 后，前缀共有 WW 种选法，后面共有 cc 个 a。每一种前缀选法都必须排除“一个 a 也不选”的情况，因此贡献是：

W(2c−1) W\left(2^c-1\right)

而不是：

W⋅2c−1 W\cdot 2^c-1

前一个式子为每一种前缀方案排除一次空集，后一个式子只在所有组合完成后减去一次，两者只有在 W=1W=1 时才相同。

复杂度与可优化处

长度为 88 的 DP 转移对每个字符执行常数次操作，后缀 a 计数也是线性的。这两部分的时间复杂度都是 O(n)O(n)。

不过当前 AC 代码会在每个候选 h 处调用一次快速幂。一次 qpow 的复杂度为 O(log⁡n)O(\log n)，因此严格按照这份实现计算，单个字符串的最坏时间复杂度是：

O(nlog⁡n) O(n\log n)

空间复杂度为 O(n)O(n)，主要来自后缀计数数组；DP 状态只占常数空间。对于多组数据，总复杂度可以按各字符串长度分别求和。

如果预处理 pow2[k]=2k mod modpow2[k]=2^k\bmod mod，或者在从右向左扫描时同步维护对应的二次幂，就能把快速幂查询降为 O(1)O(1)，使整体时间复杂度变为 O(n)O(n)。

最终 AC 代码

点击展开/折叠 最终 AC 代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int mod = 998244353;

int t;
string temp = "nunhehheh";

ll qpow(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 DP(const string &s) {
    ll sum = 0;
    int len = (int) s.length();
    vector<int> a(len + 5, 0);
    vector<ll> dp(9, 0);
    dp[0] = 1;
    for (int i = len - 1; i >= 0; --i) {
        if (i != len - 1) {
            a[i] = a[i + 1];
        }
        if (s[i] == 'a') {
            a[i]++;
        }
    }
    for (int i = 0; i < len; ++i) {
        for (int j = 8; j >= 1; --j) {
            if (s[i] == temp[j - 1]) {
                dp[j] = (dp[j] + dp[j - 1]) % mod;
            }
        }
        if (s[i] == 'h' && dp[8]) {
            sum = (sum + dp[8] * (qpow(2, a[i]) - 1) % mod) % mod;
        }
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        cout << DP(s) << '\n';
    }
    return 0;
}

这次真正要记住的状态粒度

固定模式串的子序列计数可以用一维 DP：DjD_j 表示匹配模式串前 jj 个字符的方案数，并且转移通常要倒序进行。

但这题的关键不只是套模板，而是先确定答案如何分类。把方案按固定前缀的最后一个 h 划分后，前面的 D8D_8、当前位置和后缀的非空 a 子集分别负责三段互不重叠的下标选择，重复计数自然被消除。

以后再遇到“前缀模式 + 后缀任选字符”的结构，需要先问清两个问题：当前状态表示的是截至当前位置的累计量，还是恰好在当前位置产生的新增量；要求至少选择一个元素时，2k−12^k-1 又应该乘在什么对象上。这里的括号不是形式细节，而是计数对象本身。