OSU!

Let $E_i$ denote the expected score after the $i$-th operation. The key observation is that $(x+1)^3 - x^3 = 3x^2 + 3x + 1$. To compute this increment in expectation, maintain:

$$ \text{exp1}i = (\text{exp1}{i-1} + 1) \cdot p_i $$ $$ \text{exp2}i = (\text{exp2}{i-1} + 2 \cdot \text{exp1}_{i-1} + 1) \cdot p_i $$

Then update the total expectation:

$$ E_i = E_{i-1} + (3 \cdot \text{exp2}{i-1} + 3 \cdot \text{exp1}{i-1} + 1) \cdot p_i $$

for (int i = 1; i <= n; ++i) {
    exp1[i] = (exp1[i-1] + 1) * p[i];
    exp2[i] = (exp2[i-1] + 2 * exp1[i-1] + 1) * p[i];
    E[i] = E[i-1] + (3 * exp2[i-1] + 3 * exp1[i-1] + 1) * p[i];
}
printf("%.1f\n", E[n]);

Lights Out

Given $n$ red and $m$ green lights, the expected number of remaining red lights is $\frac{n}{m+1}$, and similarly for green lights it's $\frac{m}{n+1}$. The total expectation is their sum:

double result = 1.0 * n / (m + 1) + 1.0 * m / (n + 1);
printf("%.6f\n", result);

Classroom Change (NOIP2016)

Precompute all-pairs shotrest paths using Floyd-Warshall. Define $dp[i][j][k]$ as the minimal expected walking disatnce up to the $i$-th class, having submitted $j$ applications, with $k=1$ if the $i$-th class was applied for.

Transitions consider whether the previous or current class was applied for and account for success probabilities. Initialize base cases and iterate forward.

Reward Game (SCOI2008)

Use reverse DP with bitmasking due to small $n \leq 15$. Let $dp[i][mask]$ be the maximum expected score from round $i$ to $k$, given the set of collected items represented by $mask$.

For each item $j$, if prerequisites are satisfied ($mask$ includes required items), choose to take or skip it:

$$ dp[i][mask] += \max(dp[i+1][mask], dp[i+1][mask \cup {j}] + value_j) $$

Normalize by $n$ at each step since each item appears uniformly at random.

Catch Me If You Can (NOI2005)

Precompute shortest paths and next-step positions for the cat chasing the mouse. Use memoized recursion: $dp[u][v]$ is the expected time for the cat at $u$ to catch the mouse at $v$.

If distance $\leq 2$, return 1. Otherwise, the cat moves two steps toward the mouse, and the mouse randomly stays or moves to a neighbor. Recurse accordingly.

Probabilistic Charger (SHOI2014)

Each node can be powered by itself, its children, or its parent. Use two DFS passes:

• Upward pass: aggregate child contributions using inclusion-exclusion: $P(A \cup B) = P(A) + P(B) - P(A)P(B)$.
• Downward pass: propagate parent’s external power (excluding current subtree) back down.

The answer is the sum of final powered probabilities across all nodes.

Sum of Binary Digit Counts

Compute $\prod_{i=1}^N \text{popcount}(i)$. For each possible count $k$ of 1-bits, count how many numbers $\leq N$ have exactly $k$ ones using digit DP, then raise $k$ to that count modulo $10^7+7$.

State: $dp[pos][count][target][tight]$. Enumerate bits while tracking current count and enforcing upper bound.

Balanced Binary Numbers

Count numbers in $[L, R]$ where the count of 0s $\geq$ count of 1s in binary (ignoring leading zeros). Use digit DP with state $dp[pos][ones][leading]$, adjusting zero count based on position and leading status.

Haha Numbers

A number is "haha" if divisible by the LCM of its digits. Since LCM of digits divides 2520, track remainder modulo 2520 and compress LCM values (only 48 distinct possibilities).

State: $dp[pos][rem][lcm_id][tight]$. Traverse digits from most to least significant.

Digit Frequency (ZJOI2010)

Precompute $dp[len][digit][val]$: total occurrences of val in all len-digit numbers starting with digit.

To count occurrences in $[0, X]$, decompose $X$ into digits and sum contributions from:

• Numbers with fewer digits,
• Numbers with same length but smaller prefix,
• Exact matches where trailing part contributes additional counts.

Finally, output frequency differences between $[0, b]$ and $[0, a-1]$.