SyntaxPilot
Courses/Competitive Programming/Lesson 28

Competitive Programming · Lesson 28 of 90 · 18 min

Probability and expected value

queued

These are the notes for Competitive Programming episode 28 (probability). A ludo game where you need a 6 to start gives us probability (1/6) and the question "how many throws on average?". A die's long-run average, 3.5, gives us expected value. Then an original problem, Card Packets: a little brother tosses a coin for every chips packet and grabs it on heads; what is the expected number of different cricket cards he gets? Listing all 2^n grabs is right on the samples and gets Time Limit Exceeded at n = 40. The fix is to split the count into one indicator variable per card and add their probabilities: linearity of expectation, which works even when events depend on each other. Judges want the fractional answer printed as P · Q⁻¹ mod 998244353, which episode 22's Fermat inverse handles. A stress test checks the formula against the full listing. Part two, Collect Them All, is the famous coupon collector: a Monte Carlo simulation gives noisy decimals and TLE, while the geometric waiting time 1/p and linearity give the exact answer n · H_n. Three real bugs close the episode. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hooks

Ludo. You need a 6 to bring a piece out. One face out of six: the chance is 1/6. Some days it comes on the first throw, some days after fifteen. On average it takes 6 throws (we prove it below).

A scratch card. It wins ₹100 one time in ten and nothing otherwise. On average a card is worth ₹100 · 1/10 = ₹10. If it costs ₹20, you lose ₹10 per card in the long run.

Shuffled answer sheets. A teacher hands 30 answer sheets back in a random order. Each student gets their own sheet with chance 1/30. On average exactly 30 · 1/30 = 1 student gets their own sheet, even though the events depend on each other (if you got yours, nobody else can have it).

Cricket cards in chips packets. Every packet holds one random card out of n players. The first packet is always new; with 3 of 4 cards in hand, only 1 packet in 4 helps. Collecting all 4 takes 25/3 ≈ 8.33 packets on average.

Probability

Probability is the chance of an event, written as a fraction:

P(event) = favourable outcomes / total outcomes
  • One die: P(6) = 1/6. P(even) = 3/6 = 1/2 (faces 2, 4, 6).
  • Two dice: 6 · 6 = 36 outcomes. A sum of 7 happens in 6 of them (1+6, 2+5, 3+4, 4+3, 5+2, 6+1), so P(sum 7) = 6/36 = 1/6.
  • A probability is between 0 (never) and 1 (certain).
  • This counting rule needs every outcome to be equally likely (a fair die, a fair coin).
  • Independent events (separate coin tosses) multiply: P(two heads) = 1/2 · 1/2 = 1/4.

Expected value

A random variable X is a number that depends on luck (the face of a die, the number of cards grabbed). Its expected value E[X] is its average over very many tries:

E[X] = Σ value · P(X = value)

One die: (1 + 2 + 3 + 4 + 5 + 6) · 1/6 = 21/6 = 3.5. You never actually roll a 3.5: "expected" means the long-run average, not the most likely result.

Problem E · Card Packets

Problem E · Card Packets (written for this course). A shelf has n chips packets; packet i holds the card of player ai. For every packet your little brother tosses a fair coin and grabs the packet on heads (all tosses independent). Print the expected number of different cards he gets. The answer is a fraction P/Q; print P · Q⁻¹ mod 998244353.

Input: n, then a1 … an. 1 ≤ n ≤ 2·10^5, 1 ≤ ai ≤ n, time limit 2 seconds.

Sample input Sample output Why
3 / 1 1 2 748683266 5/4
4 / 1 2 3 4 2 four cards, each grabbed with chance 1/2
5 / 3 3 3 3 3 31195137 31/32: missed only if all 5 coins are tails
1 / 1 499122177 1/2

Brute force: list every grab (Time Limit Exceeded)

Bit i of a mask m (episode 17) says whether packet i was grabbed. All 2^n grabs are equally likely, so the answer is the total number of different cards over all grabs, divided by 2^n. Under the mod, dividing by 2^n means multiplying by its inverse (episode 22).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 998244353;

ll power(ll a, ll b) {          // episode 21: a^b % MOD
    ll r = 1;
    for (a %= MOD; b > 0; b >>= 1, a = a * a % MOD)
        if (b & 1) r = r * a % MOD;
    return r;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    ll total = 0;          // different cards, over all grabs
    for (ll m = 0; m < (1LL << n); m++) {
        set<int> s;
        for (int i = 0; i < n; i++)
            if (m >> i & 1) s.insert(a[i]);
        total += s.size();
    }
    // average = total / 2^n = total · (2^n)^(-1)
    cout << total % MOD * power(power(2, n), MOD - 2) % MOD << "\n";
    return 0;
}
Input Output
3 / 1 1 2 748683266
4 / 1 2 3 4 2
5 / 3 3 3 3 3 31195137
40 / 1 2 3 … 40 Time Limit Exceeded

Why: 40 coins give 2^40 ≈ 1.1·10^12 grabs, each with 40 packets to check. For n = 2·10^5 the number of grabs, 2^200000, has 60206 digits. We need the average without listing outcomes.

Indicator variables

Look at packets 1 1 2 and all 8 grabs (- = tails):

grab --- 1-- -1- --2 11- 1-2 -12 112 average
different cards 0 1 1 1 1 2 2 2 10/8
X1 (card 1 grabbed) 0 1 1 0 1 1 1 1 6/8
X2 (card 2 grabbed) 0 0 0 1 0 1 1 1 4/8

An indicator variable is a 0-or-1 switch: 1 if an event happens, 0 if not. Its expected value is just the probability of the event: E[X] = 1 · P + 0 · (1 − P) = P. In every column, different cards = X1 + X2, so the averages add too: 6/8 + 4/8 = 10/8 = 5/4.

Linearity of expectation

E[X + Y] = E[X] + E[Y]          always
  • Two dice: each averages 3.5, so the sum averages 7.
  • It holds even when X and Y depend on each other. Shuffled answer sheets: let Xi = 1 if student i gets their own sheet. P(Xi = 1) = 1/n, so E[X1 + … + Xn] = n · 1/n = 1, for every n, although the Xi are dependent.
  • The contest recipe: write the count you want as a sum of indicators, one per "thing"; the expected count is the sum of their probabilities. No outcome is ever listed.

For Problem E, one indicator per card value v. If v appears in cnt[v] packets, it is missed only if all cnt[v] coins show tails (independent, so the halves multiply):

P(v grabbed) = 1 − (1/2)^cnt[v]
E[different] = Σ over values v that appear of 1 − (1/2)^cnt[v]

1 1 2:  (1 − 1/4) + (1 − 1/2) = 3/4 + 1/2 = 5/4

Printing a fraction: P · Q⁻¹ mod 998244353

When the answer is a fraction P/Q, problems ask for P · Q⁻¹ mod p: the unique number x with Q · x ≡ P (mod p). It behaves exactly like P/Q under +, − and ×.

  • 998244353 = 119 · 2^23 + 1 is prime (the favourite modulus on AtCoder, and common on Codeforces), so every Q not divisible by it has an inverse, Q^(p−2) by Fermat (episode 22).
  • 1/2 → power(2, MOD - 2) = 499122177.
  • 5/4 → 5 * power(4, MOD - 2) % MOD = 748683266. Check: 4 · 748683266 mod p = 5.
  • 25/3 → 332748126. Check: 3 · 332748126 mod p = 25.

The accepted solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 998244353;

ll power(ll a, ll b) {          // episode 21: a^b % MOD
    ll r = 1;
    for (a %= MOD; b > 0; b >>= 1, a = a * a % MOD)
        if (b & 1) r = r * a % MOD;
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> cnt(n + 1);          // values are 1 .. n
    for (int i = 0, x; i < n; i++) { cin >> x; cnt[x]++; }
    ll half = power(2, MOD - 2);    // 1/2 mod p
    ll ans = 0;
    for (int v = 1; v <= n; v++) {
        if (cnt[v] == 0) continue;
        ll miss = power(half, cnt[v]); // (1/2)^cnt: never grabbed
        ans = (ans + 1 - miss + MOD) % MOD;
    }
    cout << ans << "\n";
    return 0;
}
Input Output
3 / 1 1 2 748683266 (5/4)
4 / 1 2 3 4 2
5 / 3 3 3 3 3 31195137 (31/32)
1 / 1 499122177 (1/2)
n = 200000, ai = i mod 1000 + 1 (built inside main) 317011632 (= 1000 · (1 − 2^−200)), instantly

+ MOD before the last % MOD matters: ans + 1 - miss can be negative, and in C++ % of a negative number is negative.

A stress test

Episode 5's recipe: compare the formula with the full 2^n listing on 1000 random tiny inputs. Both return mod values, so they can be compared directly (comparing doubles would need a tolerance).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
ll power(ll a, ll b) {
    ll r = 1;
    for (a %= MOD; b > 0; b >>= 1, a = a * a % MOD)
        if (b & 1) r = r * a % MOD;
    return r;
}
ll brute(vector<int>& a) {         // all 2^n grabs
    int n = a.size();
    ll total = 0;
    for (int m = 0; m < (1 << n); m++) {
        set<int> s;
        for (int i = 0; i < n; i++)
            if (m >> i & 1) s.insert(a[i]);
        total += s.size();
    }
    return total % MOD * power(power(2, n), MOD - 2) % MOD;
}
ll fast(vector<int>& a) {          // linearity
    map<int, int> cnt;
    for (int x : a) cnt[x]++;
    ll half = power(2, MOD - 2), ans = 0;
    for (auto [v, c] : cnt)
        ans = (ans + 1 - power(half, c) + MOD) % MOD;
    return ans;
}
int main() {
    mt19937 rng(28);
    for (int t = 1; t <= 1000; t++) {
        vector<int> a(rng() % 12 + 1);
        for (int &x : a) x = rng() % a.size() + 1;
        if (brute(a) != fast(a)) { cout << "mismatch " << t; return 0; }
    }
    cout << "all 1000 tests passed";
}

Real output: all 1000 tests passed.

Part 2 · Problem E2 · Collect Them All

Problem E2 · Collect Them All (written for this course). A chips brand puts one of n different cards in every packet, each card equally likely. Print the expected number of packets you must buy to own all n cards, as P · Q⁻¹ mod 998244353.

Input: n. 1 ≤ n ≤ 10^6.

Samples: 1 → 1, 2 → 3, 4 → 332748126 (25/3).

First attempt: a Monte Carlo simulation

A Monte Carlo simulation estimates an average by playing out many random examples. Here: 100000 pretend shoppers, each buying random packets until they own every card.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    mt19937 rng(28);
    const int T = 100000;            // simulated shoppers
    ll total = 0;                    // packets bought by all of them
    for (int t = 0; t < T; t++) {
        vector<bool> have(n);
        int got = 0;
        while (got < n) {
            int c = rng() % n;          // a random card
            total++;
            if (!have[c]) { have[c] = true; got++; }
        }
    }
    cout << fixed << setprecision(4) << (double)total / T << "\n";
    return 0;
}
Input Output Exact
4 8.3377 25/3 = 8.3333…
2 2.9931 3
1000000 Time Limit Exceeded one shopper alone needs about 14 million packets

Close, but not exact (another seed gives other decimals), too slow, and the judge wants 332748126, which no decimal can produce. Simulation is still a fine tool for checking a formula on small n.

Geometric waiting time: 1/p

Ludo: each throw is a 6 with p = 1/6. Let E be the expected number of throws. You always make one throw; with chance 5/6 it fails and you are back at the start, expecting E more:

E = 1 + (5/6) · E   →   E/6 = 1   →   E = 6

In general, if each try succeeds with probability p (independently), the expected number of tries is 1/p. This is the geometric waiting time.

The coupon collector: n · H_n

Split the hunt into stages. While you hold k cards, a packet is new with probability (n − k)/n, so that stage lasts n/(n − k) packets on average. The total is the sum of the stages, and linearity adds their averages:

cards held 0 1 2 3
P(new), n = 4 4/4 3/4 2/4 1/4
expected wait 1 4/3 2 4

1 + 4/3 + 2 + 4 = 25/3 ≈ 8.33. In general

E = n/n + n/(n−1) + … + n/1 = n · (1 + 1/2 + … + 1/n) = n · H_n

H_n is the harmonic number; it grows like ln n + 0.577, so H_(10^6) ≈ 14.39 and a million cards take about 14.4 million packets.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 998244353;

ll power(ll a, ll b) {          // episode 21: a^b % MOD
    ll r = 1;
    for (a %= MOD; b > 0; b >>= 1, a = a * a % MOD)
        if (b & 1) r = r * a % MOD;
    return r;
}

int main() {
    ll n;
    cin >> n;
    ll h = 0;                        // H_n = 1 + 1/2 + ... + 1/n
    for (ll i = 1; i <= n; i++)
        h = (h + power(i, MOD - 2)) % MOD;
    cout << n % MOD * h % MOD << "\n";
    return 0;
}
Input Output
1 1
2 3 (the simulation said 2.9931)
4 332748126 (25/3)
500000 769981003
1000000 697618461 in about 0.13 s

Complexity vs the constraints

Approach Time Worst case here Verdict
List every grab (Problem E) O(2^n · n log n) n = 40 already ≈ 10^12 · 40 TLE
Monte Carlo (Problem E2) O(T · n ln n) 10^5 · 1.4·10^7 ≈ 1.4·10^12 TLE, and only approximate
Indicators + linearity (Problem E) O(n log n) (one fast power per card) ≈ 4·10^6 instant
n · H_n with Fermat inverses (Problem E2) O(n log MOD) 10^6 · 30 = 3·10^7 ≈ 0.13 s

Memory: O(n). (E2 can even be O(n) time with the linear inverse table used in the Python solution below.)

The rule: when the outcomes explode, write the answer as a sum of small pieces (indicators, or stages), find each piece's expected value, and add.

Common mistakes (and the real outputs)

Bug 1: 1 / 2 in integers

    ll half = 1 / 2;                // "one half"

3 / 1 1 2 → 2 (expected 748683266). Integer 1 / 2 is 0, so every "miss" probability became 0 and every card counted as surely grabbed. Fix: power(2, MOD - 2).

Bug 2: doubles, then cast and mod

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll MOD = 998244353;

int main() {
    ll n;
    cin >> n;
    double e = 0;                    // n/1 + n/2 + ... + n/n
    for (ll i = 1; i <= n; i++)
        e += (double)n / i;
    cout << (ll)e % MOD << "\n";       // cast, then mod
    return 0;
}

Input 4 → 8 (expected 332748126). The double 8.333… is cast down to 8. A fraction mod p is not "the integer part, mod p".

Bug 3: no % MOD while adding

        h += power(i, MOD - 2);          // no % here
    ...
    cout << n * h % MOD << "\n";

Input 500000 → -763160602 (expected 769981003). h grows to about 2.5·10^14, n · h ≈ 1.25·10^20 overflows long long (max ≈ 9.2·10^18), wraps to a negative number, and % of a negative is negative. (Input 4 still prints the right 332748126, so small tests hide this bug.)

Summary table

Mistake What you see Why Fix
ll half = 1 / 2; 2 instead of 748683266 integer division gives 0 power(2, MOD - 2)
cout << (ll)e % MOD; 8 instead of 332748126 a double throws the fraction away P · Q⁻¹ % MOD
h += power(i, MOD - 2); -763160602 instead of 769981003 n · h overflows long long % MOD after every + and ×
simulate and average 8.3377 instead of 25/3 random noise, and slow linearity, exact
list all 2^n outcomes Time Limit Exceeded 2^n grows too fast indicators
ans + 1 - miss without + MOD -249561087 on 1 1 2 C++ % keeps the sign (ans + 1 - miss + MOD) % MOD

Mini project

Build a small "expected value lab": (1) a function frac(P, Q) returning P · Q⁻¹ mod 998244353; (2) an exact brute force that lists every outcome for tiny inputs and returns the expected value as an exact fraction (use __int128 or Python's fractions); (3) a Monte Carlo estimator with a fixed seed; (4) the formula. Run all three on Problem E for n ≤ 12 and on the coupon collector for n ≤ 8, print them side by side, and check that the brute force and the formula agree exactly while the simulation is only close.

Practice

These follow the video's homework.

  1. Answer sheets. n students get their n answer sheets back in a uniformly random order. Expected number of students who get their own sheet?

    Answer Indicator Xi = 1 if student i gets sheet i; P = 1/n. Linearity: n · 1/n = <b>1</b> for every n ≥ 1 (checked by listing all permutations for n = 1 … 6). Print <code>1</code>. The events are dependent, and it doesn't matter.

  2. Expected sum of a random subset. Packet i is worth ai rupees; your brother grabs each packet with a coin toss. Expected total value? Example: 3 5 10.

    Answer Indicator per packet: E = Σ ai · 1/2 = (3 + 5 + 10) / 2 = <b>9</b> (checked over all 8 grabs). Mod p: (Σ ai mod p) · 499122177 % p.

  3. All six faces. Expected number of throws of a fair die until you have seen every face?

    Answer Coupon collector with n = 6: 6 · H_6 = 6 · 49/20 = 147/10 = <b>14.7</b>; mod 998244353 that is <code>99824450</code>.

  4. Problem E with a biased coin. Heads comes up with probability x/y. Example: 1 1 2 with p = 1/3.

    Answer P(v grabbed) = 1 − (1 − x/y)^cnt[v]. Here (1 − 4/9) + 1/3 = 5/9 + 3/9 = <b>8/9</b> → <code>554580197</code> (checked over all 8 grabs with exact fractions). In code: q = (y − x) · y⁻¹ mod p, then add 1 − q^cnt.

  5. Without code: two throws of a die. Expected number of different faces seen?

    Answer One indicator per face: P(face seen) = 1 − (5/6)^2 = 11/36. Six faces: 66/36 = <b>11/6</b>. Check: 6 of the 36 outcomes are doubles (1 face), 30 have 2 faces: (6 + 60)/36 = 11/6.

Quick quiz

Four packets all hold card 2; each is grabbed on a coin toss. Expected number of different cards?

A) 1/2 · B) 15/16 · C) 2 · D) 1

Answer

B. One card, so one indicator: 1 − (1/2)^4 = 15/16 (checked over all 16 grabs). C adds 1/2 per packet, but four copies of one player count as one card. D forgets that all four coins can be tails.

Interview questions

  1. What is the expected value of a random variable? The probability-weighted average of its values, Σ value · P(value): its long-run average.
  2. State linearity of expectation. Does it need independence? E[X + Y] = E[X] + E[Y] for any random variables; no independence needed. (E[X · Y] = E[X] · E[Y] does need independence.)
  3. What is an indicator variable and why is it useful? A 0/1 variable for an event; its expectation equals the event's probability, so a count written as a sum of indicators has expectation Σ probabilities.
  4. Expected number of fixed points of a random permutation? 1, by linearity: n indicators each with probability 1/n.
  5. Expected tries until the first success with probability p? 1/p (geometric distribution).
  6. What is the coupon collector result? n · H_n ≈ n ln n draws to see all n coupons.
  7. How do you print a probability modulo a prime? As P · Q⁻¹ mod p, with Q⁻¹ = Q^(p−2) by Fermat's little theorem; never with / or doubles.
  8. Why is 998244353 popular? It is prime, so inverses exist, and it equals 119 · 2^23 + 1, which also makes it suitable for the number-theoretic transform.

Glossary

Term Meaning Example
Outcome One possible result of a random experiment the die shows 4
Event A set of outcomes "the die shows an even number"
Probability favourable outcomes / total outcomes (equally likely outcomes) P(6) = 1/6
Equally likely Every outcome has the same chance a fair coin
Independent events One doesn't change the chance of the other; probabilities multiply two coin tosses: 1/4
Random variable A number that depends on luck the number of cards grabbed
Expected value E[X] Σ value · probability: the long-run average one die: 3.5
Indicator variable 1 if an event happens, else 0; E = P(event) X1 = card 1 grabbed
Linearity of expectation E[X + Y] = E[X] + E[Y], even for dependent X, Y 30 shuffled sheets → 1 own sheet
Dependent events One affects the other's chance your sheet vs your friend's sheet
Monte Carlo simulation Estimating an average by running many random trials 8.3377 for 25/3
Geometric waiting time Expected tries until a success of probability p: 1/p ludo 6: 6 throws
Coupon collector Expected draws to see all n items: n · H_n 4 cards: 25/3
Harmonic number H_n 1 + 1/2 + … + 1/n ≈ ln n + 0.577 H_4 = 25/12
P · Q⁻¹ mod p How a fraction P/Q is printed modulo a prime 5/4 → 748683266
998244353 A prime modulus, 119 · 2^23 + 1 AtCoder's favourite
Modular inverse Q⁻¹ The x with Q · x ≡ 1 (mod p); Q^(p−2) by Fermat 2⁻¹ = 499122177
Stress test Compare a fast solution with a brute force on many random small tests all 1000 tests passed
Integer overflow A value too big for its type wraps around n · h → -763160602

Summary

  • Probability = favourable / total (for equally likely outcomes). Expected value = Σ value · probability, the long-run average (one die: 3.5).
  • Listing all 2^n outcomes is right but hopeless: TLE at n = 40.
  • Write the count as a sum of indicators; by linearity of expectation its expected value is the sum of their probabilities, even for dependent events. Problem E: Σ 1 − (1/2)^cnt[v].
  • Print fractions as P · Q⁻¹ mod 998244353, with Q⁻¹ = power(Q, MOD − 2): 5/4 → 748683266.
  • A chance p per try means 1/p tries on average; collecting all n cards takes n · H_n packets (25/3 for n = 4, 697618461 mod p for n = 10^6). Simulation gave 8.3377: close, never exact.
  • Real bugs: 1 / 2 in integers (2), doubles then cast (8), a missing % MOD (-763160602).

Solutions in C++, Java and Python

Problem E · Card Packets

C++: the accepted solution above.

Java (tested on all four samples and on the n = 200000 case: 317011632). It reads input with a small hand-written reader, since Scanner is slow for 2·10^5 numbers.

import java.io.*;
import java.util.*;

public class Main {
    static final long MOD = 998244353;

    static long power(long a, long b) {
        long r = 1;
        a %= MOD;
        for (; b > 0; b >>= 1, a = a * a % MOD)
            if ((b & 1) == 1) r = r * a % MOD;
        return r;
    }

    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = nextInt(in);
        int[] cnt = new int[n + 1];
        for (int i = 0; i < n; i++) cnt[nextInt(in)]++;
        long half = power(2, MOD - 2), ans = 0;
        for (int v = 1; v <= n; v++) {
            if (cnt[v] == 0) continue;
            long miss = power(half, cnt[v]);
            ans = (ans + 1 - miss + MOD) % MOD;
        }
        System.out.println(ans);
    }

    static int nextInt(DataInputStream in) throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + (b - '0'); b = in.read(); }
        return r;
    }
}

Python (same tests, all match; about 0.05 s for n = 2·10^5). Python's % never returns a negative number, so no + MOD is needed, and pow(b, e, MOD) is the built-in fast power.

import sys

MOD = 998244353

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    cnt = [0] * (n + 1)
    for x in data[1:1 + n]:
        cnt[int(x)] += 1
    half = pow(2, MOD - 2, MOD)
    ans = 0
    for c in cnt:
        if c:
            ans = (ans + 1 - pow(half, c, MOD)) % MOD   # Python's % is never negative
    print(ans)

main()

Problem E2 · Collect Them All

C++: the program above.

Java (tested: 1 → 1, 2 → 3, 4 → 332748126, 500000 → 769981003, 1000000 → 697618461):

import java.util.*;

public class Coupon {
    static final long MOD = 998244353;

    static long power(long a, long b) {
        long r = 1;
        a %= MOD;
        for (; b > 0; b >>= 1, a = a * a % MOD)
            if ((b & 1) == 1) r = r * a % MOD;
        return r;
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        long h = 0;                       // H_n mod p
        for (long i = 1; i <= n; i++) h = (h + power(i, MOD - 2)) % MOD;
        System.out.println(n % MOD * h % MOD);
    }
}

Python (same tests, all match; about 0.3 s for n = 10^6). It computes all inverses 1 … n in O(n) with the recurrence inv[i] = −(p div i) · inv[p mod i], which is faster than n separate pow calls.

import sys

MOD = 998244353

def main():
    n = int(sys.stdin.readline())
    # inverses of 1..n in O(n): inv[i] = -(MOD // i) * inv[MOD % i]
    inv = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        inv[i] = (MOD - MOD // i) * inv[MOD % i] % MOD
    h = sum(inv[1:n + 1]) % MOD
    print(n % MOD * h % MOD)

main()