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, thena1 … 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.
-
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. -
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. -
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>. -
Problem E with a biased coin. Heads comes up with probability x/y. Example:
1 1 2with 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. -
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
- What is the expected value of a random variable? The probability-weighted average of its values, Σ value · P(value): its long-run average.
- 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.)
- 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.
- Expected number of fixed points of a random permutation? 1, by linearity: n indicators each with probability 1/n.
- Expected tries until the first success with probability p? 1/p (geometric distribution).
- What is the coupon collector result? n · H_n ≈ n ln n draws to see all n coupons.
- 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. - 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,
697618461mod p for n = 10^6). Simulation gave8.3377: close, never exact. - Real bugs:
1 / 2in 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()