Planar Reflections -- CF 1498C

Difficulty: 1600 * Techniques: DP, state design (planes x energy), symmetry collapse Problem Link

Quick Revisit

• PROBLEM: Count particles exiting after reflections between n planes, starting with energy k
• KEY INSIGHT: Don't simulate particles. Define dp[i][j] = exits from one particle with i planes ahead, energy j. Direction collapses by symmetry.
• RECURRENCE: dp[i][j] = dp[i-1][j] + dp[i-1][j-1], with dp[0][j] = dp[i][0] = 1. Answer = dp[n][k].
• TRANSFER: Exponential blowup of objects => DP by state, not individual tracking. Use symmetry to drop redundant state dimensions.

First Read

$n$ parallel planes, a particle with energy $k$ enters from the left. When hitting a plane, it passes through, but a copy with energy $k-1$ is reflected back. Particles with energy 0 don't spawn copies. Count total particles that exit (from either side).

Constraints: $n\le 1000$, $k\le 1000$. Answer modulo ${10}^9+7$.

The Simulation Disaster

My first reaction: simulate every particle. Each plane hit doubles the live count, so after $n$ planes we'd have up to $2^n$ particles. With $n\le 1000$ that's $2^{1000}$. Dead.

The right move on exponential blowup is count by state, don't track individuals. So I need a DP whose state is small.

First Attempt at State Design (and Why It Stalled)

I tried "$dp[b][e]$ = number of particles with energy $e$ after $b$ total bounces." That sounds clean but it misses direction: a particle with energy $e$ at bounce $b$ could be moving left or right, and the future planes it will hit depend on which. Trying to add direction to the state then forced me to track which plane each wave was at, and the state ballooned.

The fix is to collapse direction by symmetry. Once you stop following individual trajectories and instead ask "given a single particle that has $i$ planes ahead and energy $j$, how many particles eventually exit?", the geometry of left vs. right disappears -- both directions look the same locally.

The State That Works

Let

$$dp[i][j]=\text{total particles exiting, starting from a single particle with }i\text{ planes ahead and energy }j.$$

When that particle hits the next plane:

• It passes through with $i-1$ planes still ahead and energy $j$, contributing $dp[i-1][j]$.
• If $j>0$, it spawns a copy with energy $j-1$ going the other way. The copy now plays the same game in the other direction with one less energy, contributing $dp[i-1][j-1]$ by the symmetry above.

Base cases:

• $dp[0][j]=1$: no planes ahead means the particle just exits.
• $dp[i][0]=1$: energy 0 never spawns, so it just walks through the remaining planes and exits.

Recurrence:

$$dp[i][j]=dp[i-1][j]+dp[i-1][j-1](i,j\ge 1).$$

The answer is $dp[n][k]$. Cost is $O(nk)$, well inside the constraints.

Verifying the recurrence on tiny cases

• $n=2,k=1$: simulate by hand to get 3 exits. The DP gives $dp[2][1]=dp[1][1]+dp[1][0]=(dp[0][1]+dp[0][0])+1=2+1=3$. Match.
• $n=2,k=2$: simulate to get 4 exits. The DP gives $dp[2][2]=dp[1][2]+dp[1][1]=2+2=4$. Match.
• $n=3,k=2$: simulate to get 7 exits. The DP gives $dp[3][2]=dp[2][2]+dp[2][1]=4+3=7$. Match.

The "the symmetry collapses direction" claim is exactly what makes the spawn term $dp[i-1][j-1]$ legal.

The Code

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

const int MOD = 1e9 + 7;

void solve() {
    int n, k;
    cin >> n >> k;
    // dp[j] rolled over i; dp[0][j] = 1 for all j
    vector<long long> dp(k + 1, 1);
    for (int i = 1; i <= n; i++) {
        vector<long long> ndp(k + 1);
        ndp[0] = 1;
        for (int j = 1; j <= k; j++)
            ndp[j] = (dp[j] + dp[j - 1]) % MOD;
        dp = ndp;
    }
    cout << dp[k] << "\n";
}

int main() {
    int t; cin >> t;
    while (t--) solve();
}

Transfer Lesson

• Exponential blowup of objects => DP by state, not by particle -- when a process multiplies objects, you almost never simulate each one. Find the smallest state that captures their future behavior.
• Collapse direction by symmetry -- the breakthrough was realizing left-vs-right doesn't matter once you parameterize by "planes ahead." Whenever a process has a mirror symmetry, look for a state that is invariant under it.
• Pascal-shaped recurrence, but not literal Pascal -- the recurrence $dp[i][j]=dp[i-1][j]+dp[i-1][j-1]$ has the shape of Pascal's triangle, but the boundary $dp[i][0]=dp[0][j]=1$ is different from $(\genfrac{}{}{0ex}{}{i+j}{j})$. Don't be fooled by shape into trusting a closed form without verifying boundaries.
• A wrong DP is just a state that missed a feature -- here, the first attempt missed direction. When a DP feels like it's branching unpredictably, ask which physical attribute you forgot to encode.

---

See also: DP Intro | DP Thinking Framework | Pattern Recognition Guide | Practice Ladder 1400-1700