Project Euler Problem 923
A Young diagram is a finite collection of (equally-sized) squares in a grid-like arrangement of rows and columns, such t
Solution
Answer: 740759929
A staircase game can be reduced (via repeated removal of the common first row and first column) to a hook-shaped Young diagram.
Such hook games fall into two classes:
- integer-valued games;
- hot games of the form ${L \mid R}$.
Using the standard decomposition for sums of partizan games, one can classify every $(a,b,k)$-staircase with $a+b+k\le 64$, count each game type, and then perform a DP over ordered 8-tuples.
The resulting implementation reproduces the checks
$$S(2,4)=7,\qquad S(3,9)=315319,$$
and finally yields
$$S(8,64)\equiv 740759929 \pmod{10^9+7}.$$
(An independently published implementation uses the same reduction/DP strategy.)
Answer: 740759929