Raab Game II
Consider a two player game where each player has $n$ cards numbered $1, 2, \ldots, n$. On each turn both players place one of their cards on the table. The player who placed the higher card gets one point. If the cards are equal, neither player gets a point. The game continues until all cards have been played.
You are given the number of cards $n$ and the players' scores at the end of the game, $a$ and $b$. Your task is to count the number of possible games with that outcome.
There are $t$ test cases.
$1 \leq t \leq 1000$
$1 \leq n \leq 5000$
$0 \leq a, b, \leq n$
Tutorial
Let's consider the impossible cases first. We can readily find that it's impossible if and only if $a + b > n$ or $\min\left(a, b\right) = 0 \land \max\left(a, b\right) \neq 0$. This corresponds to Raab Game I.
Let $A_i$ denote the order in which Alice plays her cards, and let $B_i$ denote Bob’s cards. We can assume $A_i = i$, and then simply multiply the final answer by $n!$ at the end.
We call an index $i$ a fixed-point if $A_i = B_i$. There are $n - a - b$ fixed-points, and we have $\binom n{n - a - b} = \binom n{a + b}$ ways to choose these fixed-points. We can then ignore all fixed-points and focus only on the $a + b$ unfixed-points.
Then, you may notice the strange constraints: $n \leq 5000$. This gives us some intuition to design a preprocessing within $O\left(n^2\right)$.
Let $f_{a, b}$ denote the number of permutations of $B_i$ (with no fixed-points), such that $\#\left\{A_i < B_i\right\} = a$ and $\#\left\{A_i > B_i\right\} = b$.
Suppose we have already determined the first $a + b$ positions of $B_i$. Now we want to append a new number to the end of $B_i$. However, we cannot append $a + b + 1$ to $B_{a + b + 1}$, since that would create a fixed-point. Thus, here are two choices:
- Choose an index $i$ such that $A_i > B_i$
Move $B_i$ to $B_{a + b + 1}$ and set $B_i' = a + b + 1$. At index $i$ we have $A_i < B_i'$ and at index $a + b + 1$ we have $A_i > B_i$ so it is transformed to $f_{a + 1, b}$.
This means $f_{a + 1, b} \gets b \cdot f_{a, b}$. - Choose an index $i$ such that $A_i < B_i$
Move $B_i$ to $B_{a + b + 1}$ and set $B_i' = a + b + 1$. Similar to the description above. We will get $f_{a, b + 1} \gets a \cdot f_{a, b}$
However, we will realize that we missed a situation:
There is exactly one fixed-point at $i$ ($A_i = B_i$). Then we can set $B_i' = a + b + 1$, and move $B_i$ to $B_{a + b + 1}$.
Thus $f_{a + 1, b + 1} \gets \left(a + b + 1\right) \cdot f_{a, b}$.
The total time complexity is $O\left(n^2 + tn\right)$.
Code
lib::mint f[5001][5001];
struct Derangement {
Derangement() {
lib::mtg.init(1e9 + 7);
f[0][0] = 1;
for (int i = 0; i <= 5000; ++i) {
for (int j = 0; j <= 5000; ++j) {
if (j + 1 <= 5000) f[i][j + 1] += f[i][j] * i;
if (i + 1 <= 5000) f[i + 1][j] += f[i][j] * j;
if (i + 1 <= 5000 && j + 1 <= 5000) f[i + 1][j + 1] += f[i][j] * (i + j + 1);
}
}
}
} Derangement;
struct SNOWFLAKE {
SNOWFLAKE(int argc, char* argv[], int TEST_NUMBER) {
int n, a, b; std::cin >> n >> a >> b;
if (n < a + b || (std::min(a, b) == 0 && std::max(a, b) != 0)) {
std::cout << "0\n";
return;
}
std::cout << f[a][b] * lib::mint::binom(n, a + b) * lib::mint::fact(n) << "\n";
}
};