Card Stacking Game

Two players play a game with a deck of cards which contains $s$ suits with each suit containing $n$ cards numbered from $1$ to $n$.

Before the game starts, a set of cards (which may be empty) is picked from the deck and placed face-up on the table, with no overlap. These are called the visible cards.

The players then make moves in turn.
A move consists of choosing a card X from the rest of the deck and placing it face-up on top of a visible card Y, subject to the following restrictions:

X and Y must be the same suit;
the value of X must be larger than the value of Y.

The card X then covers the card Y and replaces Y as a visible card.
The player unable to make a valid move loses and play stops.

Let $C(n, s)$ be the number of different initial sets of cards for which the first player will lose given best play for both players.

For example, $C(3, 2) = 26$ and $C(13, 4) \equiv 540318329 \pmod {1\,000\,000\,007}$.

Find $C(10^7, 10^7)$. Give your answer modulo $1\,000\,000\,007$.

Given the complexity and huge values involved in this problem, it is not a simple task to compute a direct simulation or a dynamic programming solution. Instead, we should approach it using combinatorics and modular arithmetic.

The important part is to figure out what kind of structures the deck’s configuration should have for the first player to lose the game. If the first player is going to lose, it means that there were even moves in total which implies that the suit of every visible card must be the highest card left in that suit.

Consider a sequence that starts with any card and ends with the highest not-yet-played card of the same suit. The number of sequences of length $k$ (which start with lowest card $a$ and end with highest card $a+k-1$) is $(k-1)!$. This is because we can pick any of the $k-1$ cards to be the second card, any of the remaining $k-2$ cards to be the third and so on. Multiplying this with the number of choices for the lowest card ($n-k+1$) and choices for the suit of the sequence ($s$), we get the total count of sequences to be $s*(k-1)!*(n-k+1)$.

However, this counts sequences with same suits and overlapping cards multiple times. We would need to count these configurations only once so we subtract the count of all sequences that contain a common sequence.

The common sequence between sequences of length $k$ and $l$ ($k > l$) will of length min{$k,l$}. There are $k+l-1$ choose $k$ sequences of length $k$ and $l$ with common sequence of length $k-1$ (Proof: Consider choosing $k-1$ positions out of $k+l-1$ to create common sequence). Similar treatment can be done for all pairs of sequences of lengths $k$ and $l$ ($k \neq l$).

Finally, to count all the initial configurations of visible cards, the process repeats from sequences of length 1 through $n$, taking care of overlaps between sequences. The answer would be the count of all possible sets of sequences reduced by the sets that have overlaps and made modulo $1,000,000,007$ to prevent overflow.

To compute this, it requires a good understanding of combinatorics especially counting principles and permutations. In addition, since the figures are to the power of $10^7$, coding this solution would require efficient algorithms to compute factorials, power and multiplicative inverses and make them modulo $1,000,000,007$. Various tricks like storing factorial, inverse factorial values and using fast exponentiation can be used to improve runtime.

More Answers: