The Problem and What We Are Counting

CCPC 2021 Online F - Nun Heh Heh Aaaaaaaaaaa

We are given several strings containing only lowercase English letters. For each string, count its subsequences of the form nunhehheh followed by at least one a:

1

nunhehheh + 至少一个 a

A subsequence only requires the chosen indices to be strictly increasing; the characters need not be contiguous. Even if the resulting strings are identical, different selections of indices count separately. The answer is taken modulo $998244353$.

The number of test cases satisfies $T\le 1000$. Each string has length at most $10^5$, and the total length of all strings is at most $10^6$.

This is a fixed-pattern subsequence-counting DP problem. The code itself is short. What is worth reviewing is how to partition the choices, and how to distinguish cumulative states from states newly formed at the current position.

Partitioning by the Last h

A valid subsequence consists of two parts:

1

nunhehheh

followed by a nonempty sequence of as.

Suppose the final h of nunhehheh is chosen at position $i$, with $c_i$ occurrences of a after $i$. Each suffix a may be chosen or skipped, giving $2^{c_i}$ subsets. Excluding the empty choice leaves:

Let $f_i$ be the number of ways to choose nunhehhe before $i$. Fixing $i$ as the final h gives this many complete choices:

The total answer can therefore be written as:

This partition causes no double counting. Every valid subsequence has a unique final h in its nunhehheh, so it belongs to exactly one position $i$. Conversely, combining a choice of the first eight characters, the fixed ninth character h, and a nonempty choice of suffix as always produces a valid subsequence.

Maintaining Only the First Eight Characters

The complete fixed prefix is nunhehheh, but its last h already partitions the answer. The DP therefore only needs to maintain the preceding eight characters:

1

nunhehhe

Call this length-$8$ pattern $P$. While scanning a prefix of the original string, define $D_j$ as the number of ways to choose the first $j$ characters of $P$ from the characters scanned so far:

Here, $0\le j\le 8$. In particular, $D_0=1$, since there is exactly one way to choose the empty string: choose nothing. Initialize every other state to $0$. The implementation stores $D_j$ in dp[j].

When scanning character $s_i$, if it equals the $j$th character of $P$, append it to every choice that has already matched the first $j-1$ characters:

The corresponding one-dimensional transition is:

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;
    }
}

We must update in descending order. Suppose the pattern were nn. With an ascending update, scanning one n would first update $D_1$, then immediately use that newly updated $D_1$ to update $D_2$, effectively selecting the same original position twice. Descending updates ensure that the state on the right-hand side still comes from before the current character was added, so each position is used at most once.

When the current character is h, $D_8$ before the update is exactly the $f_i$ defined above. Semantically, we can add this position’s contribution to the answer before performing the DP transitions. The accepted code writes them in the opposite order, but the current h cannot update $D_8$, which ends in e, so the two orders are equivalent here.

Nonempty Choices of Suffix a Characters

To obtain the number of as to the right of each position, precompute suffix counts from right to left:

The implementation stores these counts in array a. Contributions are calculated only when $s_i$ is h. Although a[i] is defined as the number of as starting at $i$, it therefore equals the number starting at $i+1$ at every position where it is used.

The current position contributes:

1

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

If there is no a afterward, the expression in parentheses is $0$, and this h produces no valid choices. The binary-exponentiation result lies in $[1,mod-1]$, so subtracting one here cannot make it negative. Multiplying the two reduced factors also stays within the range of long long.

Why My First Approach Double-Counted

Initially, I maintained a state for the entire pattern: $D_9$ was the cumulative number of ways to choose nunhehheh through the current position:

Then, at each h, I tried to calculate:

1

dp[9] * 2^cntA - 1

There are two independent problems here.

First, I treated a cumulative number of completed matches as the number newly completed at the current position. $D_9$ retains every previously completed nunhehheh; those old choices remain in the state whenever another h appears. Adding the whole of $D_9$ to the answer each time makes old choices contribute repeatedly.

For example:

1

nunhehhehha

Either of the two consecutive hs can be the last character of the fixed prefix, so the correct answer is $2$. If we update the full-pattern state first and then use cumulative $D_9$ at every h, the two contributions include $1$ and $2$ complete prefixes, giving $3$ in total. The extra count is the old choice ending at the first h, counted again at the second h.

The right counting unit is to retain only the cumulative number of matches for the first eight characters, then fix the current h as the ninth. Pairing $D_8$ with the current position gives precisely the choices newly completed at that position.

The second problem is where to subtract one. Suppose that, after fixing the final h, there are $W$ choices for the prefix and $c$ occurrences of a afterward. The choice of taking no a must be excluded for every prefix choice, so the contribution is:

rather than:

The first expression excludes the empty subset once for each prefix choice. The second subtracts only once after combining all choices. They are equal only when $W=1$.

Complexity and Possible Optimization

The length-$8$ DP transition performs a constant number of operations per character, and counting suffix as is also linear. Both parts take $O(n)$ time.

However, the current accepted code calls binary exponentiation at each candidate h. One qpow call takes $O(\log n)$, so for this exact implementation, the worst-case time complexity for a single string is:

The space complexity is $O(n)$, mainly for the suffix-count array; the DP states use only constant space. For multiple test cases, sum the complexities over their respective string lengths.

Precomputing $pow2[k]=2^k\bmod mod$, or maintaining the corresponding power of two during a right-to-left scan, would reduce each power query to $O(1)$ and make the overall time complexity $O(n)$.

Final Accepted Code

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;
}

The State Granularity I Need to Remember

Fixed-pattern subsequence counting can use one-dimensional DP: $D_j$ counts ways to match the first $j$ characters of the pattern, and the transitions usually need to run in descending order.

But the key here goes beyond applying a template: first decide how to partition the answer. Once choices are classified by the final h of the fixed prefix, the earlier $D_8$, the current position, and the nonempty suffix subset of as account for three disjoint portions of the index selection. This naturally eliminates double counting.

The next time I encounter a structure consisting of a prefix pattern followed by freely chosen suffix characters, I need to ask two questions first: does the current state represent the cumulative count through this position, or only what is newly formed exactly here? And when at least one element must be selected, which quantity should $2^k-1$ multiply? The parentheses here express what is being counted; they are more than a detail of notation.