Grid Completion
Your task is to create an $n \times n$ grid whose each row and column has exactly one $\texttt A$ and $\texttt B$. Some of the characters have already been placed. In how many ways can you complete the grid?
$2 \leq n \leq 500$
Tutorial
We can abstract this problem as follows:
$p$ is a permutation such that $p_i$ indicates the column in which letter $\texttt A$ is placed in row $i$ (i.e., $s_{i, p_i} = \texttt A$).
$q$ is similar to $p$ and indicates the column in which letter $\texttt B$ is placed.
$p_i \neq q_i$ for all $i$, since both $\texttt A$ and $\texttt B$ cannot occupy the same cell.
Initially, some of $p_i$ and $q_i$ are given. Count the number of valid permutations.
Consider the principle of inclusion-exclusion. Define $f\left(x\right)$ as the number of $p$ and $q$ such that for each $i$:
- if $x_i = 0$, both $p_i = q_i$ and $p_i \neq q_i$ are valid.
- if $x_i = 1$, then $p_i = q_i$ must hold.
Then the answer will be
$$\sum\limits_{0 \leq x < 2^n} f\left(x\right)\left(-1\right)^{\operatorname{popcount}\left(x\right)}$$
If $p_i = q_i$, then one of the following conditions must hold.
- $p_i = -1$ and $q_i = -1$
- $p_i = -1$ and $q_i \neq -1$ and $q_i$ does not appear in any assigned $p_j$
- $p_i \neq -1$ and $q_i = -1$ and $p_i$ does not appear in any assigned $q_j$
Where $p_i = -1$ means $p_i$ is not given initially.
Define $c_0$ as the number of indices satisfy condition 1, $c_1$ for condition 2 and $c_2$ for condition 3.
Let $c_3$ denote the number of values that appear in neither $p$ nor $q$.
Let $pn$ and $qn$ denote the number of indices $i$ where $p_i = -1$ and $q_i = -1$, respectively.
The answer is
$$\sum\limits_{0 \leq i \leq min\left(c0, c3\right)}\sum\limits_{0 \leq j \leq c_1}\sum\limits_{0 \leq k \leq c_2}\binom{c_0}i\binom{c_1}j\binom{c_2}k\binom{c_3}i \cdot i! \cdot \left(pn - i - j\right)! \cdot \left(qn - i - k\right)!$$
Code
struct SNOWFLAKE {
SNOWFLAKE(int argc, char* argv[], int TEST_NUMBER) {
using lib::mint;
lib::mtg.init(1e9 + 7);
int n; std::cin >> n;
std::vector<std::string> s(n);
for (auto& i : s) std::cin >> i;
bsi p(n, -1);
bsi q(n, -1);
for (int i = 0; i < n; ++i) {
if (s[i].find('A') != s[i].npos) p[i] = s[i].find('A');
if (s[i].find('B') != s[i].npos) q[i] = s[i].find('B');
}
std::set<int> _c3;
for (int i = 0; i < n; ++i) _c3.insert(i);
for (auto i : p) _c3.erase(i);
for (auto i : q) _c3.erase(i);
int c0 = 0;
int c1 = 0;
int c2 = 0;
int c3 = _c3.size();
int pn = 0;
int qn = 0;
for (int i = 0; i < n; ++i) {
c0 += p[i] == -1 && q[i] == -1;
c1 += p[i] == -1 && q[i] != -1 && count(p.begin(), p.end(), q[i]) == 0;
c2 += p[i] != -1 && q[i] == -1 && count(q.begin(), q.end(), p[i]) == 0;
pn += p[i] == -1;
qn += q[i] == -1;
}
mint tar;
for (int i = 0; i <= std::min(c0, c3); ++i) {
for (int j = 0; j <= c1; ++j) {
for (int k = 0; k <= c2; ++k) {
auto a = mint::binom(c0, i);
auto b = mint::binom(c1, j);
auto c = mint::binom(c2, k);
auto d = mint::binom(c3, i);
auto e = mint::fact(i);
auto f = mint::fact(pn - i - j);
auto g = mint::fact(qn - i - k);
auto h = a * b * c * d * e * f * g;
if ((i + j + k) % 2 == 0) tar += h;
else tar -= h;
}
}
}
std::cout << tar << "\n";
}
};