Game theory and probability DP

The shape of a game problem: a second player who also wants to win

Ordinary dynamic programming asks "what is the best result I can reach?" and you control every step of the path. A game problem takes some of those steps away. After you move, someone else moves, and that someone wants the opposite outcome. You no longer choose a path through the states; you choose one edge, and the opponent chooses the next. The question changes from "what is the best path?" to "what can I guarantee, whatever they do?"

The problems in this chapter have the same five properties, and the whole method depends on them:

• Two players move in turn. Neither can skip.
• Perfect information. Both players see the whole position. There are no hidden cards.
• No chance in the moves. The only uncertainty is what the opponent chooses.
• The game must end. Every play is finite, and the rules say who wins at the end.
• Both play optimally. "Optimally" means each player makes the move that is best against a perfect opponent, not against the opponent's likely mistakes.

The second half of the chapter drops the opponent and lets chance take the next step instead: a die rolls, a knight picks a random move, soup is served at random. Those are expected-value and probability problems. They look different, but the engine is the same: define a position, define the value of a position, and write the value as a combination of the values of the positions one step later. Only the combination changes.

Read this table once more at the end. If you can say, for a new problem, which row it is, you have already chosen the state and the recurrence.

This chapter builds on the state design from advanced DP (bitmasks and intervals are the states used below) and on the memoization argument from advanced backtracking, where Can I Win appears as a memoized search. Here the question is why that search is correct, and how the same idea scales to scores, to chance and to games with piles of a billion stones.

Win and lose, derived: a position is winning exactly when some move leads to a losing one

Start with the smallest game that has all the properties. A pile holds n stones. Players alternate, and on each turn a player removes 1, 2 or 3 stones. The player who cannot move, because the pile is empty, loses (equivalently, whoever takes the last stone wins). Does the player who moves first win?

Define the words precisely, because the whole chapter rests on them. A position is winning (W) if the player about to move has a strategy that wins whatever the opponent replies. It is losing (L) if, once the player to move has moved, the other player has such a strategy whatever the mover chose. The claim is:

The proof is a short induction, and it shows precisely which assumptions you are using. Induct on the length of the longest play that can start from the position. That length is finite because the game must end.

• No move is possible. The rules decide. Here the player to move loses, so the position is L. The statement "some move leads to an L position" is false, because there are no moves. They agree.
• Some move leads to an L position q. The positions one move away are shorter, so by the induction hypothesis q is correctly labelled. L means the player not moving at q, which is the current mover, has a winning strategy from q. So the mover plays to q and then follows that strategy. The position is W.
• Every move leads to a W position. Whatever the mover plays, the opponent is now the player to move at a W position, and has a winning strategy there. Every choice of the mover loses, so the position is L, and it is not W.

The three cases cover everything, and they never give two answers for one position. That is the proof, and it is the logic behind every win/lose solution in this chapter. It also tells you what can break it. If the game can repeat a position forever, the induction has nothing to start from. If the game can end without a winner, "not winning for the opponent" no longer means "winning for me". Section after section below, the bugs in game solutions turn out to be a violated assumption from this list.

function canWinTake(n, moves) {
  const memo = new Map(); // stones left -> does the player about to move win?

  function wins(left) {
    if (left === 0) return false; // no stones: the player to move cannot move and loses
    if (memo.has(left)) return memo.get(left);
    let result = false;
    for (const take of moves) {
      if (take <= left && !wins(left - take)) { // a move that leaves the opponent in a losing position
        result = true;
        break;
      }
    }
    memo.set(left, result);
    return result;
  }

  return wins(n);
}

The base case left === 0 is the rules of the game written as code. Every other line is the proof's second and third case: the loop looks for a move whose resulting position is losing, and if none exists the answer stays false. Time is O(n · m) for m allowed moves, because each of the n positions is computed once and tries at most m moves. Space is O(n) for the memo and the recursion.

Dry run: the table for moves 1, 3 and 4, built from 0 upward

The losing positions so far are 0, 2, 7 and 9. Running the code to 40 gives 0, 2, 7, 9, 14, 16, 21, 23, 28, 30, 35, 37: a period of 7. For moves 1, 2 and 3 the losing positions are the multiples of 4. These patterns are the reason a problem with n up to 10⁹ can still be easy.

function winTable(maxN, moves) {
  const wins = new Array(maxN + 1).fill(false); // wins[n]: the player to move with n stones wins
  for (let n = 1; n <= maxN; n++) {
    for (const take of moves) {
      if (take <= n && !wins[n - take]) {
        wins[n] = true;
        break;
      }
    }
  }
  return wins;
}

When a game problem gives a huge pile, do not search for the answer directly. Print the table for the first 30 or 40 values, look at where the L positions fall, and then prove the pattern the way the proof above does: from an L position every move must land on a W position, and from a W position there must be a move onto an L position. For moves 1, 2 and 3 that is two lines: from a multiple of 4 any move of size 1 to 3 leaves a non-multiple; from a non-multiple n, taking n % 4 stones (which is between 1 and 3) leaves a multiple. That is why Nim Game is n % 4 !== 0.

The same method settles Divisor Game (start with n; a move picks x with 0 < x < n and n % x === 0 and replaces n by n - x; the player who cannot move loses). The table suggests that the player to move wins exactly when n is even. Proof: n = 1 has no move, so it is L. An odd n has only odd divisors, so every move leads to an even number. An even n can take x = 1 and lead to an odd number. By induction, even is W and odd is L. The function is one line, return n % 2 === 0, and the proof is the answer the interviewer is waiting for.

From the game tree to a table: minimax, negamax and the DP

The textbook name for this recursion is minimax. Give every finished game a score from the point of view of the player who is about to move at that position: +1 if they win, -1 if they lose. At each position the mover chooses the move with the best result for them, and the opponent then chooses the move that is best for the opponent, which is the worst for the mover. Written with two roles, that is a max level followed by a min level.

Because the game is zero-sum, one function is enough. If V(p) is the value of position p for the player to move, then after a move to q the opponent is the one to move, and what is good for them is exactly bad for me: the value of that move for me is -V(q). So there is one rule at every level:

This form is called negamax. With only the two values +1 and -1, -V(q) = +1 exactly when V(q) = -1, so the maximum is +1 exactly when some move leads to a position worth -1 to its mover. That is the statement proved above, so minimax with win/lose values and the "winning iff some move reaches a losing position" recursion are one idea. The negation -V(q) is what later lets the score-difference recurrences subtract the opponent's best, instead of maintaining a separate max level and min level.

The step from search to dynamic programming is the observation you already know from memoization. V(p) depends only on the position p, not on the sequence of moves that led there. Two different move orders that reach the same position share the same subtree, so the subtree needs solving once. The tree has about (moves per turn)^depth nodes. The table has one entry per distinct position. For the pile game with moves 1, 2 and 3, the plain recursion with early exit made 3,843,200 calls for n = 30; the memoized one made 67 calls and stored 30 results. The cost of the DP is therefore

and that product is what you quote when the interviewer asks for the complexity. Everything that follows is a choice of what "position" means, and a proof that the choice is complete.

The memo key: everything the future depends on, nothing else

A memo key is correct when two plays that reach the same key have identical futures: the same legal moves and the same results, for both players. Test a candidate key by asking two questions. Is anything missing? If two plays with equal keys could differ in what moves are legal or who wins, the key is too small and the memo will silently return wrong answers. Is anything redundant? Information that is already determined by the rest of the key only splits states that are really the same, and the memo stops sharing work.

Notice what is not in the keys: who is to move. The recursion is always written from the point of view of the player about to move. The function returns "can the player about to move win from here?" or "how far ahead can they get?", and when it recurses it either negates the result or subtracts it. Storing the player in the key would double the states for no gain, and forgetting to flip the sign at one recursive call is a classic bug.

Score games: maximize your lead, not your total

Now the game has a score. Predict the Winner: an array of numbers lies in a row. Two players alternate; on each turn a player takes the number at either end of the row and adds it to their own score. Both want the larger final score. Return whether the first player can win, where a tie counts as a win for the first player.

The obvious state is the interval (i, j) of numbers still in the row. The obvious value, "the most I can collect", is awkward: after you take nums[i] the opponent moves on (i + 1, j), and what you eventually collect from that interval depends on how the opponent plays it. The way out is to change what the table stores.

Take the left end. You gain nums[i]. The other player is now the one to move on (i + 1, j), and the best lead they can guarantee there is lead(i + 1, j). Your lead over the whole interval is your gain minus their lead on the rest: nums[i] - lead(i + 1, j). The right end gives nums[j] - lead(i, j - 1). You pick the better:

lead(i, i) = nums[i]
lead(i, j) = max( nums[i] - lead(i + 1, j),  nums[j] - lead(i, j - 1) )

Why subtracting the opponent's lead is right. Suppose I have taken nums[i]. The opponent chooses among their moves to make their own lead as large as possible. Their lead and my lead on the rest of the row are exact negatives of each other, because every number goes to exactly one of us (my score minus theirs is minus (their score minus mine)). So the move that maximizes their lead is the same move that minimizes mine, and the best they can do to me is to hold my lead on the rest to -lead(i + 1, j). There is no separate "min" step to write. That one sign flip is the whole minimax of this game. Formally the claim "lead(i, j) is what the recurrence computes" follows by induction on j - i: a one-number row is forced, and every longer row reduces to two shorter rows whose values are correct by the hypothesis.

function bestLead(piles) {
  const n = piles.length;
  const lead = Array.from({ length: n }, () => new Array(n).fill(0)); // lead[i][j]: best (mover - other) on piles i..j
  for (let i = 0; i < n; i++) lead[i][i] = piles[i];
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      lead[i][j] = Math.max(piles[i] - lead[i + 1][j], piles[j] - lead[i][j - 1]);
    }
  }
  return lead[0][n - 1];
}

function predictTheWinner(nums) {
  return bestLead(nums) >= 0; // player 1 wins a tie
}

The answer is lead(0, n - 1) >= 0; >= is the tie rule. If the problem says a tie goes to the second player, or asks for the lead itself, only that last line changes. Time is O(n²) and space is O(n²). Intervals are filled by increasing length so that the two shorter intervals are ready, exactly as in interval DP.

Dry run: nums = [5, 3, 4, 5]

lead[0][3] = 1, which is at least 0, so the first player wins by one point: 9 against 8 out of the 17 in the row (both opening moves are equally good here). I checked the code against a brute force that tracks both players' totals separately and lets each maximize their own total, on 600 random arrays that included negative numbers and zeros.

One row of memory is enough

Row i of the table needs row i + 1 (the cell below) and the cell to its left in row i. If you fill rows from the bottom up and each row from left to right, one array is enough. Before row i is computed, lead[j] still holds the value from row i + 1; the assignment overwrites it with row i, and lead[j - 1] has already been overwritten, which is exactly what the recurrence wants.

function bestLeadRolling(piles) {
  const n = piles.length;
  const lead = piles.slice(); // lead[j] holds lead[i + 1][j] until row i overwrites it with lead[i][j]
  for (let i = n - 2; i >= 0; i--) {
    for (let j = i + 1; j < n; j++) {
      lead[j] = Math.max(piles[i] - lead[j], piles[j] - lead[j - 1]); // lead[j - 1] is already row i
    }
  }
  return lead[n - 1];
}

Time stays O(n²); space drops to O(n). This is the same rolling idea as in knapsack: overwriting is safe when every cell you still need is either already the new value or not yet touched.

Stone Game: when parity answers the question

Stone Game is the same row game with an even number of piles and a total that is odd, so there is never a tie. The DP above solves it. But the answer is always true, and the reason is worth saying in an interview. Number the piles 0 to n - 1. The two ends of a row of even length have different parities. The first player takes pile 0, which has an even index. Now the row has odd length and both ends are odd-indexed, so whatever the opponent takes is an odd-indexed pile, and one end of the remaining even-length row is even-indexed again; the first player takes that. By repeating this, the first player collects every even-indexed pile, and by starting with the other end could collect every odd-indexed pile instead. One of the two sums is larger than the other, and the first player can choose it. With an odd total the sums cannot be equal, so the first player wins.

I tested the consequence on 2,000 random arrays of even length: the lead was never negative, and it was positive whenever the total was odd. The argument needs the even length. For an odd number of piles it does not work, which is why Predict the Winner, with any length, needs the DP.

Stone Game III: the same lead idea over a suffix

The piles are in a row, with values that may be negative. On each turn a player takes 1, 2 or 3 piles from the front. The player with the larger sum wins; return "Alice", "Bob" or "Tie". The position is just the index i of the first remaining pile, so the table is one-dimensional. With lead[i] the best lead for the player to move when piles i.. remain, taking k piles gains their sum and then hands the opponent lead[i + k]:

lead[n] = 0
lead[i] = max over k in 1..3 (with i + k <= n) of ( sum(i .. i + k - 1) - lead[i + k] )

function stoneGameIII(stoneValue) {
  const n = stoneValue.length;
  const lead = new Array(n + 1).fill(0); // lead[i]: best (mover - other) when stones i.. remain; lead[n] = 0
  for (let i = n - 1; i >= 0; i--) {
    let taken = 0;
    lead[i] = -Infinity;
    for (let k = 1; k <= 3 && i + k <= n; k++) {
      taken += stoneValue[i + k - 1];
      lead[i] = Math.max(lead[i], taken - lead[i + k]);
    }
  }
  if (lead[0] > 0) return "Alice";
  if (lead[0] < 0) return "Bob";
  return "Tie";
}

Dry run: stoneValue = [1, 2, 3, 7], then [1, 2, 3, -9]

lead[0] = -1 < 0, so Bob wins. Taking all three of the first piles (6 stones) is Alice's best, but it leaves Bob the 7. For [1, 2, 3, -9] the table is lead[3] = -9, lead[2] = max(3 - (-9), -6) = 12, lead[1] = max(2 - 12, 5 - (-9), -4) = 14 and lead[0] = max(1 - 14, 3 - 12, 6 - (-9)) = 15. Alice wins by taking three piles and forcing Bob onto the -9.

Time is O(n), because every index tries at most three moves, and space is O(n). The pitfalls are all in the edges: the base value lead[n] = 0 (an empty row has no lead), the guard i + k <= n so that a move never takes piles that do not exist, and -Infinity as the starting maximum so that all-negative rows still pick the least bad move. Starting lead[i] at 0 would let a player "pass", which is not a legal move. I compared the function with an exhaustive search that tracks both players' scores on 600 random rows with values from -20 to 20.

Stone Game II: when a rule depends on history, the history joins the state

Now the number of piles a player may take depends on how the game has gone. The piles are in a row with positive values. Start with M = 1. On each turn a player takes the first X remaining piles for any 1 <= X <= 2M, and then M becomes max(M, X). The game ends when the piles are gone. Return the most stones the first player can collect.

Apply the key test from before. Is i, the first remaining pile, enough? No. At the same i the legal moves depend on M: with M = 1 a player may take 1 or 2 piles, with M = 5 up to 10. So M is part of the position, and the state is (i, M). Here it is natural to store the share instead of the lead. Let best(i, M) be the most stones the player to move can collect from piles i.. onward. Every remaining stone ends up with exactly one of the two players, so after you take X piles the opponent collects at most best(i + X, max(M, X)) of the rest and you keep everything else:

best(i, M) = max over X in 1..2M of ( suffix[i] - best(i + X, max(M, X)) )

Here suffix[i] is the sum of piles i... Taking the first X piles and receiving the rest minus the opponent's share is the same as taking those piles plus your share of the remainder. The two forms (lead and share) are interchangeable because the total is a constant.

function stoneGameII(piles) {
  const n = piles.length;
  const suffix = new Array(n + 1).fill(0);
  for (let i = n - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + piles[i];
  const memo = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(-1)); // memo[i][M]

  function best(i, M) { // most stones the mover can collect from piles i.. when the limit is 2M
    if (i + 2 * M >= n) return suffix[i]; // may take everything left (piles are positive)
    if (memo[i][M] !== -1) return memo[i][M];
    let most = 0;
    for (let x = 1; x <= 2 * M; x++) {
      most = Math.max(most, suffix[i] - best(i + x, Math.max(M, x))); // my share = what is left - the opponent's share
    }
    memo[i][M] = most;
    return most;
  }

  return best(0, 1);
}

Dry run: piles = [2, 7, 9, 4, 4]

The suffix sums are 26, 24, 17, 8, 4, 0. The recursion visits these states.

The first player collects 10 of the 26 stones, by taking only the 2 first (X = 1), and the second player gets the other 16, which is exactly best(1, 1).

There are at most n² distinct (i, M) pairs (M never exceeds the number of piles) and each tries at most 2M <= 2n moves, so the time is at most O(n³) and the space O(n²). The "take everything" shortcut is valid because no pile is negative: when every remaining pile is at least 0, taking them all is the best possible share. I checked the function against an exhaustive search on 500 random arrays of positive piles.

Bitmask games: Can I Win, and why its guards matter

Two players take turns choosing an integer from 1 to maxChoosable. A number, once chosen, is gone for both players. Each chosen number is added to a shared running total, and the player whose choice makes the total reach desiredTotal or more wins. Can the first player force a win?

The backtracking chapter solves this as a memoized search. Here the same solution is read as a game. The position is which numbers have been used. The running total is not an extra fact, because it is the sum of the used numbers; whose turn it is follows from how many numbers are used. So the used set is a complete key, and with maxChoosable at most 20 an integer bitmask holds it: bit n - 1 is set when the number n is used. A winning pick is a move into a position the opponent never gets to play, so it counts as a move into a lost position for them.

function canIWin(maxChoosable, desiredTotal) {
  if (desiredTotal <= 0) return true; // the target is met before anyone has to move
  if ((maxChoosable * (maxChoosable + 1)) / 2 < desiredTotal) return false; // even every number together falls short
  const memo = new Int8Array(1 << maxChoosable); // 0 unknown, 1 win, 2 lose; index = mask of used numbers

  function wins(used, remaining) {
    if (memo[used] !== 0) return memo[used] === 1;
    let result = false;
    for (let n = 1; n <= maxChoosable && !result; n++) {
      const bit = 1 << (n - 1);
      if (used & bit) continue;
      if (n >= remaining || !wins(used | bit, remaining - n)) result = true;
    }
    memo[used] = result ? 1 : 2;
    return result;
  }

  return wins(0, desiredTotal);
}

The three early lines each need a reason, and the reasons are the interesting part.

• if ((maxChoosable * (maxChoosable + 1)) / 2 < desiredTotal) return false is a correctness line. If even the sum of all the numbers falls short, nobody can ever reach the target. The game ends with every number used and no winner, which the win/lose recursion cannot express: the loop would find no moves and return false, and the caller would read "the opponent cannot win" as "I win". The guard answers "the first player cannot force a win" directly. When the guard does not fire, a winner is guaranteed: the unused numbers always add up to at least the remaining target (they sum to the total of all numbers minus the used ones, and the total is at least the target), so while the target is still unmet there is always an unused number, and the last pick of the game must reach it. That restores the "no draws" assumption of the proof. Removing the guard changed the answer on 255 of the 700 pairs I tried (maxChoosable 1 to 10, desiredTotal 1 to 70).
• if (desiredTotal <= 0) return true is only a shortcut. With maxChoosable >= 1 the loop already finds n >= remaining on the first number and returns true. The line makes the intent visible and avoids allocating the memo.
• n >= remaining inside the loop is the move that ends the game. It does not recurse, because the game is over.

Dry run: maxChoosable = 3, desiredTotal = 4

Whatever the first player picks (1, 2 or 3), the opponent can reach 4 on the next turn. The position ({1,2}, 1) is looked up once and reused: two different orders of play reach it. Time is O(2^m · m) and space O(2^m) for m = maxChoosable, since each of the at most 2^m masks is solved once and tries at most m numbers. For m = 20 that is about 20 million steps and a 1 MB typed array. The typed array Int8Array holds 0 for "not computed yet", 1 and 2 for the two answers, which avoids a Map's hashing and its boxed values.

Flip Game II: the string is the position

A string contains only + and -. A move chooses two consecutive ++ and flips them to --. The player who cannot move loses. Can the player to move win? Here the position is the string, and the memo key is the string itself.

function canWinFlip(s) {
  const memo = new Map(); // the string itself is the position

  function wins(state) {
    if (memo.has(state)) return memo.get(state);
    let result = false;
    for (let i = 0; i + 1 < state.length && !result; i++) {
      if (state[i] === "+" && state[i + 1] === "+") {
        const next = state.slice(0, i) + "--" + state.slice(i + 2);
        if (!wins(next)) result = true; // flipping here leaves the opponent without a win
      }
    }
    memo.set(state, result);
    return result;
  }

  return wins(s);
}

Dry run: five pluses in a row

Five pluses in a row is a loss for the player to move. Every flip splits the row into pieces that the opponent can answer. There are at most 2ⁿ different strings, and each state spends O(n) positions times O(n) to build a string, so the worst case is O(2ⁿ · n²). In practice far fewer strings are reachable, but the bound is exponential, and the next two sections show why a long run of pluses can be answered much faster. I checked the function against an exhaustive search without a memo on all 16,383 strings of length 13 or less.

Nim and the XOR rule, with a proof

Nim is the standard game with several piles. There are heaps of stones. A move chooses one heap and removes any positive number of stones from it. The player who cannot move (all heaps empty) loses. A position is the multiset of heap sizes. It has too many positions to table when the heaps are large, yet there is a closed-form answer:

Proof. Call a position zero if its XOR is 0. By the win/lose recursion, it is enough to show three facts, because they say that zero positions satisfy exactly the definition of L.

• The finished position is zero. All heaps are empty and the XOR of zeros is 0, and the player to move has lost. This is the base case.
• From a zero position, every move leaves a non-zero position. A move changes exactly one heap, from h to some h' with h' < h. The new XOR is 0 ^ h ^ h', which equals h ^ h'. That is not 0 because h and h' are different numbers. So no move from a zero position reaches a zero position.
• From a non-zero position, some move reaches a zero position. Let s be the XOR, which is not 0, and let d be the highest bit that is set in s. The bit d in s is the XOR of the bit d of every heap, so an odd number of heaps have bit d set; in particular at least one does. Take such a heap h and replace it with h ^ s. Bit d goes from 1 to 0, and every bit above d is unchanged (s has none of them set), so h ^ s < h. That is a legal move, removing h - (h ^ s) stones. The new XOR is s ^ h ^ (h ^ s) = 0.

Together: from a zero position the player to move can only reach non-zero positions, which have a move back to zero; the finished position is zero. By induction on the total number of stones (it falls by at least 1 on every move), the zero positions are exactly the losing ones, which is the claim. The third fact is also an algorithm: it tells the winner which move to make.

function nimWins(heaps) {
  let xor = 0;
  for (const h of heaps) xor ^= h;
  return xor !== 0; // the player to move wins exactly when the XOR is not zero
}

function nimMove(heaps) {
  let xor = 0;
  for (const h of heaps) xor ^= h;
  if (xor === 0) return null; // already losing: no move helps against best play
  for (let i = 0; i < heaps.length; i++) {
    const target = heaps[i] ^ xor; // the size this heap needs for the XOR to become 0
    if (target < heaps[i]) return [i, heaps[i] - target]; // [heap index, stones to remove]
  }
}

Dry run: heaps [3, 4, 5]

The XOR is 2, so the player to move wins. The highest set bit of 2 is bit 1, and only the heap of size 3 has it. The target size is 3 ^ 2 = 1, smaller than 3, so the move is to remove 2 stones from heap 0. The new heaps [1, 4, 5] are 001, 100 and 101, whose XOR is 0. For the heap of size 4, 4 ^ 2 = 6 is larger, so it offers no move. Deciding takes O(m) for m heaps. I checked nimWins and the move that nimMove returns against an exhaustive search of the whole game tree, over 5,043 heap vectors: one or two heaps of up to 9 stones each, three heaps of up to 7, four of up to 5 and five of up to 4.

Sprague-Grundy in one section: games that split into independent parts

This section is awareness, not something to derive in an interview. The idea is that Nim's XOR rule is one case of a general rule. Give every position of a game a number, its Grundy value, by this definition: the Grundy value of a position is the smallest non-negative integer that is not the Grundy value of any position one move away (the mex, the "minimum excludant"). A position with no moves has value 0. Two facts follow, and the theorem behind them is stated here without proof:

• A position is losing exactly when its Grundy value is 0. (If the value is 0, no move leads to a 0, so every move leads to a W position. If the value is not 0, some move leads to a position with value 0.)
• If a game is a sum of independent games, where on each turn a player moves in exactly one of them, then its Grundy value is the XOR of the parts' values.

A Nim heap of size n can move to every size from 0 to n - 1, so its value is mex{0, ..., n - 1} = n. A game of several heaps is a sum of heaps, so its value is the XOR of the sizes: the rule from the last section is the special case. Anywhere a game falls apart into pieces that do not interact, you can compute a value per piece and XOR them, instead of searching the product of all the pieces' positions.

Flip Game II is such a game. Each run of consecutive pluses is a piece: flipping two neighbouring pluses in a run of length len leaves two runs, of lengths left and len - 2 - left, and the pieces never affect one another. The value of a run follows the mex rule over the ways to split it:

function flipGrundy(maxLen) {
  const g = new Array(maxLen + 1).fill(0); // g[len]: Grundy value of a run of len pluses
  for (let len = 2; len <= maxLen; len++) {
    const reachable = new Set();
    for (let left = 0; left <= len - 2; left++) {
      reachable.add(g[left] ^ g[len - 2 - left]); // flip two pluses: the run splits into left and len - 2 - left
    }
    let mex = 0;
    while (reachable.has(mex)) mex++; // smallest value that no move reaches
    g[len] = mex;
  }
  return g;
}

function canWinFlipFast(s) {
  const runs = s.split("-").map((run) => run.length); // lengths of the runs of pluses
  const g = flipGrundy(runs.reduce((a, b) => Math.max(a, b), 0));
  let xor = 0;
  for (const len of runs) xor ^= g[len];
  return xor !== 0;
}

Dry run: the first Grundy values of a run of pluses

The values for lengths 0 to 20 are 0, 0, 1, 1, 2, 0, 3, 1, 1, 0, 3, 3, 2, 2, 4, 0, 5, 2, 2, 3, 3. A run of 5 has value 0, matching the dry run of "+++++" above: it is a loss for the player to move. The code reads a whole string as its list of runs (s.split("-")) and XORs their values; it is O(n + L²) for a longest run of L, because the table is built once, and L² is small next to 2ⁿ. I checked canWinFlipFast against the memoized search on all 16,383 strings of length 13 or less and on 300 random strings of lengths 14 to 23.

Expected value: linearity first, then DP

From here the second player is replaced by chance, and the question changes from "who wins" to "what happens on average". The expected value of a random quantity is its probability-weighted average, the sum of each possible value times its probability. There are two tools. The first is often a one-line answer; the second is a DP and works when the first does not.

Linearity of expectation. For any two random quantities X and Y, E[X + Y] = E[X] + E[Y]. No independence is needed. That makes counting problems easy to attack: write the quantity as a sum of indicator variables, each 1 when some event happens and 0 when it does not, and use E[indicator] = P(event). You never need to understand how the events interact.

Example: fixed points of a random permutation. Shuffle the numbers 0 to n - 1 uniformly. How many positions i have the number i in them, on average? Let Xi be 1 if position i holds the number i. Position i is equally likely to hold any of the n numbers, so P(Xi = 1) = 1/n. The sum of n indicators has expected value n · (1/n) = 1, for every n. The indicators are not independent (if the first n - 1 positions are fixed, so is the last), and the answer is the same, which is the point of the method. I confirmed it by enumerating every permutation for n from 1 to 7: the total number of fixed points across all n! permutations is exactly n!.

Example: the coupon collector. There are n kinds of coupon. Each draw gives a uniformly random kind, independently. How many draws are needed on average to see every kind? Split the process into phases. Phase have starts when have kinds are already seen and ends when a new kind arrives. A draw is new with probability p = (n - have) / n. The number of draws until the first success, with success probability p, averages 1 / p. (Reason: call the average E. One draw is made; with probability 1 - p you are back where you started, so E = 1 + (1 - p) E, which gives E = 1 / p.) The total is the sum of the phase lengths, so by linearity

E = n/n + n/(n-1) + ... + n/1 = n * (1 + 1/2 + ... + 1/n)

function expectedDrawsToCollect(n) {
  let expected = 0;
  for (let have = 0; have < n; have++) {
    expected += n / (n - have); // waiting for one of the n - have new coupons: geometric with p = (n - have) / n
  }
  return expected;
}

Dry run: three kinds of coupon

For n = 10 the answer is about 29.29, and for n = 25 about 95.4. The last coupon alone costs n draws on average, which is why collecting everything is much slower than collecting most of it. I checked the formula against an independent computation that tracks the probability of finishing on each draw and sums t · P(finish at t) for n = 1, 2, 3, 6, 10 and 25; they agree to 1e-8. Time is O(n).

Expected value by DP: the value of a state is the cost of a step plus the weighted next values

When the process is a walk through states, define E[s] as the expected number of remaining steps from state s. At a finished state it is 0. Otherwise one step is taken, which costs 1, and the next state is random, so

E[s] = 1 + sum over outcomes o of ( P(o) * E[next state after o] )

This is the same shape as the game recursions, with a probability-weighted sum in place of a max. If the states can never repeat, the recursion ends and you fill the table from the finished states backwards.

A walk that never repeats. Roll a fair six-sided die repeatedly and add the faces. How many rolls are needed on average until the total is at least target? The total only goes up, so a state is the current total s, and E[s] = 0 for any s >= target.

function expectedRollsToReach(target) {
  const expected = new Array(target + 6).fill(0); // expected[s]: rolls still needed from total s; 0 once s >= target
  for (let s = target - 1; s >= 0; s--) {
    let sum = 0;
    for (let face = 1; face <= 6; face++) sum += expected[s + face];
    expected[s] = 1 + sum / 6;
  }
  return expected[0];
}

The array is padded by 6 zeros so that expected[s + face] past the target reads 0 without a branch. For target = 3: E[2] = 1 + (0 + 0 + ... ) / 6 = 1, then E[1] = 1 + (E[2] + 0 + 0 + 0 + 0 + 0) / 6 = 7/6, then E[0] = 1 + (E[1] + E[2] + 0 + 0 + 0 + 0) / 6 = 1 + (7/6 + 1) / 6 = 49/36, about 1.361. Time and space are O(target). I compared the function against the probability of finishing at each roll, summed as t · P(finish at t), for targets 1, 2, 6, 7, 20 and 50, and they agree to 1e-9.

A walk that loops back. Roll a die until a six appears twice in a row. Now a state is the length of the current run of sixes, 0 or 1, and a failed roll sends you back to 0, so the states form a cycle and "fill from the end" has no end to start from. The fix is algebra. Write the two equations:

E0 = 1 + (1/6) E1 + (5/6) E0         one roll: a six moves to run 1, anything else stays at run 0
E1 = 1 + (1/6) * 0 + (5/6) E0        a six finishes, anything else falls back to run 0

Substitute the second into the first: E0 = 1 + 1/6 + (5/36) E0 + (5/6) E0. Collecting terms, E0 (1 - 5/36 - 30/36) = 7/6, so E0 / 36 = 7/6 and E0 = 42. For a run of any length k, the trick is to express each E[j] as a + b · E0 from the top down, so that the cycle becomes a single equation in E0:

function expectedRollsForRun(k) {
  let a = 0; // E[j] = a + b * E[0], worked out from the top: E[k] = 0
  let b = 0;
  for (let j = k - 1; j >= 0; j--) {
    a = 1 + a / 6; // one more roll, then a six (1/6) climbs to j + 1
    b = b / 6 + 5 / 6; // any other face (5/6) falls back to run length 0
  }
  return a / (1 - b); // E[0] = a + b * E[0], solved for E[0]
}

Every state above the top is built from the one before it: E[k] = 0 is a = 0, b = 0, and going down one step gives a' = 1 + a/6 (the roll that costs 1, then a six), and b' = b/6 + 5/6 (a six keeps the dependence, anything else returns to E0). At j = 0, E0 = a + b · E0, so E0 = a / (1 - b). The exact answers for k = 1 to 6 are 6, 42, 258, 1554, 9330 and 55,986, which fit (6k+1 - 6) / 5. I checked k = 1 to 3 against the finishing-time distribution too. Time is O(k).

Probability DP: push the probability forward, one step at a time

The second kind of question is "what is the probability that...". The state table now holds, for each step t, the probability of being in each state after t steps. Start with probability 1 on the initial state. Each step moves every state's probability along its transitions, multiplied by the chance of the transition. The probability of an event is the sum, over all the ways it can happen, of the product of the step probabilities along the way; the table adds up all the ways that reach the same state.

This is the forward direction. The expected-value tables of the last section were filled backwards, from the finished states. Both are valid; pick the direction that gives the question's answer directly. The cost is (steps) × (states) × (transitions per state). Two rules keep these tables honest. Probability that leaves the table for good (a knight that falls off the board) is simply dropped, or collected into an answer counter, and never carried on. And the probabilities at any step add up to the starting 1 minus whatever has left; if the totals do not, something was double-counted.

Knight Probability in a Chessboard

A knight starts on an n × n board at (row, column). It makes exactly k moves. Each move picks one of the 8 knight moves uniformly, even if that move leaves the board, and once the knight is off the board it stays off. What is the probability that it is still on the board after k moves? Layer t of the table is the chance of being on each cell after t moves while never having left.

function knightProbability(n, k, row, column) {
  const moves = [[1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1], [-2, 1], [-1, 2]];
  let now = Array.from({ length: n }, () => new Array(n).fill(0)); // now[r][c]: chance of being on (r, c) and still on the board
  now[row][column] = 1;
  for (let step = 0; step < k; step++) {
    const next = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        if (now[r][c] === 0) continue;
        for (const [dr, dc] of moves) {
          const nr = r + dr;
          const nc = c + dc;
          if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue; // this move leaves the board: its probability is dropped
          next[nr][nc] += now[r][c] / 8;
        }
      }
    }
    now = next;
  }
  let total = 0;
  for (const line of now) for (const p of line) total += p;
  return total;
}

Dry run: n = 3, k = 2, start (0, 0), written as counts out of 8^t

The answer is 4/64 = 0.0625. The code divides by 8 at each step, which gives the same result as dividing by 8^k once at the end. Time is O(k · n² · 8) and space O(n²), two layers. I checked the function against a direct count of all 8^k move sequences on 120 random boards (n from 1 to 6, k from 0 to 5) and the results agree to 1e-12.

Out of Boundary Paths: count the paths, divide by nothing

A ball starts at (startRow, startColumn) of an m × n grid and moves up, down, left or right, at most maxMove times. Count the paths that take the ball out of the grid, modulo 1,000,000,007. This is the same table as the knight, with counts instead of probabilities, and the mass that leaves is not dropped but added to the answer at the step where it leaves. A path is counted once, at the first move that exits, because after exiting it is no longer in the table.

function findPaths(m, n, maxMove, startRow, startColumn) {
  const MOD = 1000000007;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let ways = Array.from({ length: m }, () => new Array(n).fill(0)); // ways[r][c]: paths that are on (r, c) after this many moves
  ways[startRow][startColumn] = 1;
  let out = 0;
  for (let move = 0; move < maxMove; move++) {
    const next = Array.from({ length: m }, () => new Array(n).fill(0));
    for (let r = 0; r < m; r++) {
      for (let c = 0; c < n; c++) {
        const w = ways[r][c];
        if (w === 0) continue;
        for (const [dr, dc] of dirs) {
          const nr = r + dr;
          const nc = c + dc;
          if (nr < 0 || nr >= m || nc < 0 || nc >= n) out = (out + w) % MOD; // this path leaves the grid now
          else next[nr][nc] = (next[nr][nc] + w) % MOD;
        }
      }
    }
    ways = next;
  }
  return out;
}

Dry run: m = 2, n = 2, maxMove = 2, start (0, 0)

The answer 6 matches the example in the problem statement. Time is O(maxMove · m · n · 4) and space O(m · n). Taking the remainder after every addition is needed once the counts get large, and it is safe: each count is below 1,000,000,007 and a sum of two of them is below 2³¹, far under the exact-integer limit of doubles (2⁵³). I checked the function against full path enumeration on 150 small cases, and against a BigInt run with no remainder (reduced at the end) on grids up to 50 × 50 with 50 moves.

Dice Roll Simulation: the state remembers how long the current run is

A die with faces 1 to 6 is rolled n times, and face i may not appear more than rollMax[i] times in a row. Count the different sequences, modulo 1,000,000,007. The last face alone is not enough to know which next rolls are allowed; you also need how many times in a row it has come up. So the state is (last face, run length), and the table holds how many sequences end in each state.

Two kinds of transition. Repeating the last face moves (face, run) to (face, run + 1) when run + 1 <= rollMax[face]. Rolling any other face starts a run of 1 and is allowed for every face that is not the same as the last. Summing over "any other face" for each target face would be a loop inside a loop; instead note that the number of sequences that end in some other face is all - endsIn[face], which is O(1) to get after one pass.

function dieSimulator(n, rollMax) {
  const MOD = 1000000007;
  let dp = rollMax.map((limit) => new Array(limit + 1).fill(0)); // dp[face][run]: sequences ending in face with exactly run of them in a row
  for (let face = 0; face < 6; face++) dp[face][1] = 1;
  for (let roll = 2; roll <= n; roll++) {
    const endsIn = dp.map((runs) => runs.reduce((sum, count) => (sum + count) % MOD, 0));
    const all = endsIn.reduce((sum, count) => (sum + count) % MOD, 0);
    const next = rollMax.map((limit) => new Array(limit + 1).fill(0));
    for (let face = 0; face < 6; face++) {
      next[face][1] = (all - endsIn[face] + MOD) % MOD; // switching to this face from any other face starts a run of 1
      for (let run = 2; run <= rollMax[face]; run++) next[face][run] = dp[face][run - 1]; // repeating the face lengthens the run
    }
    dp = next;
  }
  let total = 0;
  for (const runs of dp) for (const count of runs) total = (total + count) % MOD;
  return total;
}

Dry run: n = 2, rollMax = [1, 1, 2, 2, 2, 3]

The answer for these limits is 34, matching the problem's example. Time is O(n · (sum of the limits)), at most about 90n since each limit is at most 15, and space O(sum of the limits). I verified it on 120 random small cases (n up to 7, limits from 1 to 4) against direct enumeration of every allowed sequence, and against a BigInt version with no remainder up to n = 5000.

Soup Servings: a cutoff that is justified by the numbers

There are two soups, A and B, with n ml each. Each turn picks one of four servings, each with probability 1/4, as (A, B) amounts: (100, 0), (75, 25), (50, 50), (25, 75). If a soup has less than the serving asks for, it gives what is left. The process stops when a soup is empty. Return the probability that A empties first plus half the probability that they empty in the same turn. An answer within 1e-5 is accepted, and n can be 10⁹.

Every serving is a multiple of 25 ml, so count in units of 25: the servings are (4, 0), (3, 1), (2, 2), (1, 3) units, and an amount n is ceil(n / 25) units (a leftover of 1 ml still blocks the soup from being empty). With f(a, b) for the answer when A has a units and B has b:

f(a, b) = 0.5   if a <= 0 and b <= 0     (both empty together: half a win)
f(a, b) = 1     if a <= 0               (A emptied first)
f(a, b) = 0     if b <= 0               (B emptied first)
f(a, b) = 0.25 * ( f(a-4, b) + f(a-3, b-1) + f(a-2, b-2) + f(a-1, b-3) )

That is U² states for U = n / 25, which is about 1.6 · 10¹⁵ for n = 109. There is a way out, and it is the interesting part.

Why a cutoff is valid. Each turn removes on average (100 + 75 + 50 + 25) / 4 = 62.5 ml from A, but only (0 + 25 + 50 + 75) / 4 = 37.5 ml from B. A drains faster, and the longer the process runs the more likely it is that A is empty first, so the answer approaches 1 as n grows. Because the problem accepts an error of 1e-5, any n so large that the true answer is within 1e-5 of 1 may return 1. I computed the exact values and measured how far below 1 the answer is:

The cutoff of 4,800 is safe for two reasons that must both hold. The error at 4,800 is 5.0 · 10^-6, below 1e-5. And the answer does not move away from 1 for larger n: I checked numerically, for every n up to 55,000 (the answer depends on n only through ceil(n / 25)), that the answer never decreases as n grows. That check is evidence, not a proof; the drift argument above is why you would expect it, and why the gap falls so quickly. Below the cutoff the table has at most 192² = 36,864 states.

function soupServings(n) {
  if (n >= 4800) return 1; // beyond this the answer is within 1e-5 of 1
  const units = Math.ceil(n / 25); // every serving is a multiple of 25 ml, so count in units of 25
  const memo = Array.from({ length: units + 1 }, () => new Array(units + 1).fill(-1));

  function f(a, b) { // P(A empties first) + half of P(both empty together), with a and b units left
    if (a <= 0 && b <= 0) return 0.5;
    if (a <= 0) return 1;
    if (b <= 0) return 0;
    if (memo[a][b] !== -1) return memo[a][b];
    memo[a][b] = 0.25 * (f(a - 4, b) + f(a - 3, b - 1) + f(a - 2, b - 2) + f(a - 1, b - 3));
    return memo[a][b];
  }

  return f(units, units);
}

Dry run: n = 50, so 2 units each

The answer for n = 50 is 0.625, as in the problem statement. I compared the function with a direct enumeration of the game in raw millilitres, with no memo, for every n from 0 to 150. Below the cutoff the table has U² entries for U = ceil(n / 25), at most 192² = 36,864, so time and space are constant in n once the cutoff is applied.

New 21 Game: probability DP with a sliding window

Alice starts with 0 points. While she has fewer than k points she draws a number uniformly from 1 to maxPts and adds it. She stops when she has k points or more. What is the probability that her final total is at most n?

Let reach[i] be the probability that her total ever equals i. She reaches i by being at some total j that is still below k (so she draws again) and then drawing exactly i - j, which has probability 1 / maxPts. So

reach[0] = 1
reach[i] = (1 / maxPts) * sum of reach[j] over j in [i - maxPts, i - 1] with j < k

The answer is the sum of reach[i] for k <= i <= n, because those are exactly the totals at which she stops. The sum for reach[i] has maxPts terms, so computing every entry that way costs O(n · maxPts). But the range slides: the sum for i + 1 is the sum for i plus the new term reach[i] (if i < k) minus the term that fell out, reach[i - maxPts] (if it was in the window). A running window sum makes each step O(1).

function new21Game(n, k, maxPts) {
  if (k === 0 || n >= k + maxPts - 1) return 1; // no draw is made, or no total can exceed n
  const reach = new Array(n + 1).fill(0); // reach[i]: chance that Alice's total ever equals i
  reach[0] = 1;
  let window = 1; // sum of reach[j] over the last maxPts totals j < k, the ones that still draw
  let answer = 0;
  for (let i = 1; i <= n; i++) {
    reach[i] = window / maxPts;
    if (i < k) window += reach[i]; // Alice draws again from i
    else answer += reach[i]; // Alice stops at i, and i <= n
    if (i - maxPts >= 0 && i - maxPts < k) window -= reach[i - maxPts]; // total i - maxPts is too far back to reach i + 1
  }
  return answer;
}

Dry run: n = 5, k = 3, maxPts = 4

The probability is 0.921875. The only other final total is 6, reached from 2 by drawing a 4, with probability reach[6] = 0.078125; it exceeds n = 5 and is the missing 1 - 0.921875. I compared the function with exact fractions on 400 random cases (the largest difference was 9 · 10^-16) and on one with n = 200, k = 150 and maxPts = 100, where the float answer differs from the exact fraction by about 3 · 10^-16. Time is O(n) and space O(n).

Floating point, exact fractions and answers modulo a prime

Every probability table in this chapter fills cells with a number, a 64-bit double, and most of the time that is exactly what a judge expects: the problem says "answers within 10^-5 are accepted" and a double carries about 15 to 16 significant digits. It is worth knowing where that stops being true, because probability problems are where JavaScript's number type is most often misused.

What the double does to you

• Rounding is built in. 0.1 + 0.2 is 0.30000000000000004, so 0.1 + 0.2 === 0.3 is false. Compare computed probabilities with a tolerance, Math.abs(a - b) < 1e-9, never with ===. That includes the checks in your own tests.
• Small errors do not stay invisible. The loop-back expected value from earlier, expectedRollsForRun(2), returns 42.00000000000015, not 42, and expectedRollsForRun(3) returns 258.00000000000506. If the true answer is a known integer or a short fraction, an exact computation is the way to show it.
• Very small values vanish. 0.5 ** 1074 is 5e-324, the smallest positive double, and 0.5 ** 1075 is 0. So is 8 ** -400, which a knight with 400 moves would produce on one path. A table that sums many paths loses only the cells that are individually tiny, but an answer that is itself that small cannot be returned as a double.
• Cutoffs are tolerance-dependent. The Soup Servings shortcut is right for an error limit of 1e-5 and wrong for a stricter one, as computed above.
• How big the error gets, in these experiments. The knight table was within 6 · 10^-17 of the exact value on 200 random boards (n from 3 to 10, k up to 60), and the New 21 Game within 9 · 10^-16 on 400 random cases. The expected-value result of about 258 was off by 5 · 10^-12, which is a relative error near 2 · 10^-14. That is evidence for these sizes, not a bound for every input.

Exact answers: count outcomes first, divide once

A judge may ask for an exact fraction, or for the probability written as P / Q modulo a prime, or two probabilities may have to be compared exactly. Then doubles are the wrong tool. The cleanest approach is usually to change what the table counts. In the knight problem every step has 8 outcomes, all equally likely, so the probability after k moves is (number of move sequences that stay on the board) / 8k. Count sequences with BigInt, which has no upper limit, and divide once at the end. This is the same table as before with the division by 8 removed:

function knightWays(n, k, row, column) {
  const moves = [[1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1], [-2, 1], [-1, 2]];
  let now = Array.from({ length: n }, () => new Array(n).fill(0n)); // now[r][c]: how many move sequences are on (r, c) and still on the board
  now[row][column] = 1n;
  for (let step = 0; step < k; step++) {
    const next = Array.from({ length: n }, () => new Array(n).fill(0n));
    for (let r = 0; r < n; r++) {
      for (let c = 0; c < n; c++) {
        if (now[r][c] === 0n) continue;
        for (const [dr, dc] of moves) {
          const nr = r + dr;
          const nc = c + dc;
          if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
          next[nr][nc] += now[r][c];
        }
      }
    }
    now = next;
  }
  let total = 0n;
  for (const line of now) for (const ways of line) total += ways;
  return total;
}

For n = 3, k = 2 from (0, 0) it returns 4n, and 4/64 reduced is exactly 1/16. When the denominators differ from step to step, as in expected values, use small fraction helpers on BigInt. The numerator and denominator are kept in lowest terms by dividing by their greatest common divisor:

function gcd(a, b) {
  while (b !== 0n) [a, b] = [b, a % b];
  return a;
}

function frac(num, den = 1n) {
  const g = gcd(num < 0n ? -num : num, den);
  return g === 0n ? { num: 0n, den: 1n } : { num: num / g, den: den / g }; // lowest terms, den > 0
}

const add = (x, y) => frac(x.num * y.den + y.num * x.den, x.den * y.den);
const mul = (x, y) => frac(x.num * y.num, x.den * y.den);
const compare = (x, y) => {
  const diff = x.num * y.den - y.num * x.den;
  return diff < 0n ? -1 : diff > 0n ? 1 : 0;
};

With those helpers the loop-back expected value is exact. The same algebra as before, with 1/6 and 5/6 as exact fractions, returns 42 with no trace of the error:

function expectedRollsForRunExact(k) {
  let a = frac(0n);
  let b = frac(0n);
  for (let j = k - 1; j >= 0; j--) {
    a = add(frac(1n), mul(frac(1n, 6n), a));
    b = add(mul(frac(1n, 6n), b), frac(5n, 6n));
  }
  const oneMinusB = add(frac(1n), mul(frac(-1n), b));
  return mul(a, frac(oneMinusB.den, oneMinusB.num)); // a / (1 - b)
}

expectedRollsForRunExact(2) returns { num: 42n, den: 1n }, and for k = 1 to 6 it returns 6, 42, 258, 1554, 9330 and 55,986 exactly. Exact arithmetic costs more: the numbers grow with the number of steps. For the knight on an 8 × 8 board with 100 moves from (0, 0), the reduced fraction has a 77-digit numerator and a 90-digit denominator. That is still instant here, but it is why you count with a fixed denominator when you can, instead of reducing a fraction after every addition.

Answers modulo 1,000,000,007

Many counting problems ask for the result modulo the prime 1,000,000,007. Counts reduce at every step, which is fine for additions with plain numbers, as in the paths and dice tables. Two things change when probabilities are involved or numbers are multiplied.

• Multiplying two reduced numbers can lose bits. 1000000006 * 1000000006 is about 10¹⁸, above 2⁵³, so the double is only approximate: 1000000006 * 1000000006 % 1000000007 gives 999999972, while the true value is 1 (it is (-1) times (-1) modulo the prime). Do products in BigInt and convert back with Number(...).
• Division becomes multiplication by an inverse. A probability p / q is reported as p * q-1 modulo the prime, where the inverse of q is qM - 2 modulo M (Fermat's little theorem, valid because M is prime and q is not a multiple of it).

const MOD = 1000000007n;

function powMod(base, exponent, mod) {
  let result = 1n;
  base %= mod;
  while (exponent > 0n) {
    if (exponent & 1n) result = (result * base) % mod;
    base = (base * base) % mod;
    exponent >>= 1n;
  }
  return result;
}

const inverse = (a) => powMod(a, MOD - 2n, MOD);
const asModular = (x) => (x.num % MOD) * inverse(x.den) % MOD;

asModular(frac(1n, 16n)) is 562500004n, and 16 * 562500004 = 9,000,000,064, which leaves remainder 1 after dividing by 1,000,000,007, as an inverse must. Reduce numerators and denominators consistently: either reduce the fraction first and then convert, or convert numerator and denominator separately; both give the same residue as long as the denominator is not a multiple of the prime.

Choosing the number type

Recognising a game or probability problem

These problems announce themselves in the statement, and the first job is to name the family, because the family fixes the value you store.

• "Two players take turns", "both play optimally", "can the first player win", "Alice and Bob" → a win/lose or score game. If the answer is true/false, store a boolean per position. If the answer is a score or "who has more", store the lead of the player to move.
• Elements are taken from the ends of a row, or from the front, with a choice of how many → interval or suffix state, and the lead recurrence gain - best lead of the opponent.
• A pool of at most about 20 distinct items that cannot be reused → the used set is the state, a bitmask. Check the "someone must win" condition before trusting the recursion.
• A pile of up to 10⁹ items, or several piles with take-any-number moves → do not build a table of that size. Print the first 30 values, find the pattern (period, parity, XOR of sizes) and prove it with the "from L every move reaches W, from W some move reaches L" argument.
• The board falls apart into independent pieces (runs, separate piles) → the Grundy value of each piece, XORed.
• "Expected number of", "on average how many" → try linearity of expectation first, with indicators. If the process is a walk through states, E[s] = 1 + sum of P(o) * E[next]; if states can repeat, write the equations and solve for the start state.
• "What is the probability that... after k steps" or "until a condition" → push the distribution forward over the states, step by step, and collect the mass at the end or the mass that leaves.
• "Return the answer modulo 1,000,000,007" with probabilities → count outcomes with integers and divide by a modular inverse; "within 1e-5" → doubles are fine, and look for a cutoff when n is huge.

Who is the other player? This is the question that separates the two halves of the chapter. If the other side is an adversary who wants you to lose, its step is a min over its choices (in negamax, a sign change). If the other side is random, its step is an average. A problem that mixes both, say a game where a die decides the move, takes a max on your turns and an average on the die's, and it is still a DP over positions with the same state tests.

A routine that works in an interview. (1) Say which family it is. (2) Define the position and test the key: could two plays with the same key differ? (3) Write the recurrence from the point of view of the player about to move. (4) State the base case from the rules, and confirm the game cannot end without a winner and cannot loop. (5) State the complexity as positions times work per position. (6) Test on two or three tiny inputs by hand, or against an exhaustive search, before the interviewer does it for you. Step 6 is how every function in this chapter was checked.