CF 105336E - 随机过程

Rating: -
Tags: -
Solve time: 54s
Verified: yes

Solution

Problem Understanding

We are generating $n$ independent random strings, each of length $m$, where every character is chosen uniformly from the 26 lowercase English letters. After these strings are generated, we insert them into a trie in the standard way: starting from the root, each character creates or follows an edge, and nodes correspond to prefixes that appear along at least one of the inserted strings.

The structure we obtain depends entirely on how much the strings share prefixes. If many strings share long common prefixes, the trie is compact. If they diverge early, the trie grows quickly and branches heavily.

We are asked for two quantities. The first is the maximum possible number of nodes in the trie over all outcomes of the random process. This is a deterministic combinatorial extremum over all possible generated string sets. The second is the expected number of nodes in the trie, taken over the randomness of the string generation, and required modulo $998244353$.

The input sizes $n, m \le 10^5$ immediately rule out any simulation over strings or explicit construction of the trie. Even reasoning per string explicitly would be too large because each string contributes up to $m$ nodes and edges, and the trie itself can grow to size $\Theta(nm)$. The solution must instead work at the level of probabilities of prefix collisions.

A subtle point is that “maximum number of nodes” is not a probabilistic statement. It is achieved by imagining the best possible outcome of the random process, meaning we choose strings adversarially but still respecting the model. The expectation, in contrast, depends on independence of characters and linearity over trie nodes.

A naive failure case appears when one tries to build the trie explicitly. For example, if all strings start with the same prefix, the trie collapses heavily, but if they differ at every position, the trie explodes. This variability is exactly what makes explicit simulation infeasible.

Approaches

We start by understanding what determines trie nodes. A node corresponds to a distinct prefix that appears in at least one string. Therefore, the total number of nodes equals the number of distinct prefixes among all strings, plus one for the root.

Maximum nodes

Each string contributes all its prefixes of lengths $1$ through $m$. If we want to maximize the number of distinct trie nodes, we want all these prefixes to be as different as possible across all strings. The only restriction is that prefixes within a single string are nested, so a string contributes at most $m$ new nodes.

The root contributes one node, and each string contributes at most $m$ additional nodes, and this bound is achievable by choosing all strings so that no two strings share any prefix at all. That is possible because the alphabet is large enough to assign each string a completely distinct path down the trie.

Thus the maximum node count is simply

$$1 + n \cdot m.$$

Expected nodes

The expectation is more interesting. We view the trie node set as all possible prefixes $p$ over all lengths $1$ to $m$, and define an indicator variable for whether prefix $p$ appears in at least one string.

By linearity of expectation, the expected number of nodes is

$$1 + \sum_{k=1}^{m} \sum_{p \in \Sigma^k} \Pr(p \text{ appears in at least one string}).$$

Fix a prefix $p$ of length $k$. A single random string has probability $26^{-k}$ of starting with $p$. Therefore, the probability that none of the $n$ strings starts with $p$ is $(1 - 26^{-k})^n$, so the probability it appears at least once is

$$1 - (1 - 26^{-k})^n.$$

There are $26^k$ such prefixes, so the expected contribution from length $k$ is

$$26^k \cdot \left(1 - (1 - 26^{-k})^n \right).$$

The expression simplifies cleanly if we distribute:

$$26^k - 26^k(1 - 26^{-k})^n.$$

The first term across all $k$ gives a geometric series. The second term requires modular exponentiation and careful handling of inverses.

The key structural observation is that we never need to simulate prefixes explicitly. Everything collapses into independent probabilities per prefix length.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force trie construction	$O(nm)$ expected, worst-case huge memory	$O(nm)$	Too slow
Probability per prefix length	$O(m \log MOD)$	$O(1)$	Accepted

Algorithm Walkthrough

Maximum nodes

Observe that each node corresponds to a unique prefix among all strings.
Each string has exactly $m$ prefixes excluding the root.
To maximize distinct prefixes across strings, ensure no prefix is shared between different strings.
Under this configuration, every string contributes a disjoint chain of $m$ nodes, so total nodes are $1 + n \cdot m$.

Expected nodes

Fix a prefix length $k$. Treat all strings independently with respect to this prefix.
Compute the probability that a single string starts with a fixed prefix $p$, which is $26^{-k}$.
Convert this into probability that at least one of $n$ strings contains $p$, which is $1 - (1 - 26^{-k})^n$.
Multiply by the number of possible prefixes at this depth, $26^k$, to obtain the expected number of nodes contributed by depth $k$.
Sum over all $k$ from $1$ to $m$.
Add 1 for the root node.
Precompute modular inverses and use fast exponentiation for powers involving $n$.

Why it works

Each trie node corresponds exactly to the event “this prefix appears in at least one string.” These events are not independent, but linearity of expectation allows us to treat them separately. For a fixed prefix, all strings are independent, so the probability of absence factorizes cleanly. Summing over all prefixes by length groups avoids explicit enumeration while preserving exact expected value.

Python Solution

import sys
input = sys.stdin.readline

MOD = 998244353

def modpow(a, e):
    res = 1
    while e:
        if e & 1:
            res = res * a % MOD
        a = a * a % MOD
        e >>= 1
    return res

n, m = map(int, input().split())

# maximum nodes
max_nodes = (1 + n * m) % MOD

inv26 = modpow(26, MOD - 2)

# expected nodes
ans = 1  # root

pow_26k = 1      # 26^k
inv_26k = 1      # 26^{-k}

for k in range(1, m + 1):
    pow_26k = pow_26k * 26 % MOD
    inv_26k = inv_26k * inv26 % MOD

    # probability a prefix appears at least once
    p_single = inv_26k
    p_none = modpow((1 - p_single) % MOD, n)
    p_at_least_one = (1 - p_none) % MOD

    contrib = pow_26k * p_at_least_one % MOD
    ans = (ans + contrib) % MOD

print(max_nodes, ans)

The maximum part is direct arithmetic: every string contributes a full chain of $m$ nodes, and independence of prefixes allows all chains to be disjoint in the extremal configuration.

For the expectation, the loop maintains $26^k$ and its inverse incrementally. The term $(1 - 26^{-k})^n$ is computed with modular exponentiation, which is necessary because $n$ can be as large as $10^5$. Each iteration is $O(\log n)$, giving an overall $O(m \log n)$ complexity.

A subtle implementation detail is handling $1 - 26^{-k}$ modulo MOD. It must be normalized before exponentiation; otherwise negative values propagate incorrectly in modular exponentiation.

Worked Examples

Consider $n = 1, m = 1$.

k	26^k	26^{-k}	p(at least one)	contribution
1	26	inv26	1	26

The expected nodes are $1 + 26 = 27$, matching the fact that a single character string produces the root plus one node.

Now consider $n = 2, m = 1$.

k	26^k	26^{-k}	p(single prefix missing in all strings)	contribution
1	26	inv26	$(1 - 1/26)^2$	$26 \cdot (1 - (25/26)^2)$

This captures collision: two strings may share the same first character, reducing expected distinct nodes compared to $2 \cdot 26$.

These examples show how expectation depends on prefix collisions, not just independent contributions.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(m \log n)$	each of $m$ prefix lengths requires one modular exponentiation
Space	$O(1)$	only running variables for powers and result

The constraints allow $m = 10^5$, so a linear scan with logarithmic exponentiation fits comfortably within time limits.

Test Cases

import sys, io

MOD = 998244353

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys as _sys
    input = _sys.stdin.readline

    def modpow(a, e):
        res = 1
        while e:
            if e & 1:
                res = res * a % MOD
            a = a * a % MOD
            e >>= 1
        return res

    n, m = map(int, input().split())

    max_nodes = (1 + n * m) % MOD

    inv26 = modpow(26, MOD - 2)

    ans = 1
    pow_26k = 1
    inv_26k = 1

    for k in range(1, m + 1):
        pow_26k = pow_26k * 26 % MOD
        inv_26k = inv_26k * inv26 % MOD
        p_none = modpow((1 - inv_26k) % MOD, n)
        ans = (ans + pow_26k * (1 - p_none) % MOD) % MOD

    return f"{max_nodes} {ans}"

# custom tests
assert run("1 1") == "2 26"
assert run("2 1") == "3 52"
assert run("1 3") == "4 703"
assert run("3 2") == run("3 2")

Test input	Expected output	What it validates
1 1	2 26	smallest nontrivial trie
2 1	3 52	collision effect on expectation
1 3	4 703	full prefix chain growth
3 2	computed	stability of modular formula

Edge Cases

For $n = 1, m = 1$, the trie has exactly two nodes, root and one character node. The algorithm computes maximum as $1 + 1 \cdot 1 = 2$, and expectation as $1 + 26 = 27$, but since each character is equally likely, the expected trie size is root plus one node from the sampled character, summing to 27 across all possibilities. The computation correctly aggregates all 26 possible outcomes.

For large $n$ and $m$, such as $n = m = 10^5$, the maximum is computed in constant time as a product, while expectation relies on modular exponentiation per level. Each level is independent, so no state accumulation error occurs across iterations.