Bingo
Contest: Codeforces Round 733 (Div. 1 + Div. 2, based on VK Cup 2021 - Elimination (Engine))
Difficulty rating: 2600
Tags: bitmasks, combinatorics, dp, math, probabilities

Getting ready for VK Fest 2021, you prepared a table with $$$n$$$ rows and $$$n$$$ columns, and filled each cell of this table with some event related with the festival that could either happen or not: for example, whether you will win a prize on the festival, or whether it will rain.

Forecasting algorithms used in VK have already estimated the probability for each event to happen. Event in row $$$i$$$ and column $$$j$$$ will happen with probability $$$a_{i, j} \cdot 10^{-4}$$$. All of the events are mutually independent.

Let's call the table winning if there exists a line such that all $$$n$$$ events on it happen. The line could be any horizontal line (cells $$$(i, 1), (i, 2), \ldots, (i, n)$$$ for some $$$i$$$), any vertical line (cells $$$(1, j), (2, j), \ldots, (n, j)$$$ for some $$$j$$$), the main diagonal (cells $$$(1, 1), (2, 2), \ldots, (n, n)$$$), or the antidiagonal (cells $$$(1, n), (2, n - 1), \ldots, (n, 1)$$$).

Find the probability of your table to be winning, and output it modulo $$$31\,607$$$ (see Output section).

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 21$$$) — the dimensions of the table.

The $$$i$$$-th of the next $$$n$$$ lines contains $$$n$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$ ($$$0 < a_{i, j} < 10^4$$$). The probability of event in cell $$$(i, j)$$$ to happen is $$$a_{i, j} \cdot 10^{-4}$$$.

Output format:
Print the probability that your table will be winning, modulo $$$31\,607$$$.

Formally, let $$$M = 31\,607$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

Note:
In the first example, any two events form a line, and the table will be winning if any two events happen. The probability of this is $$$\frac{11}{16}$$$, and $$$5927 \cdot 16 \equiv 11 \pmod{31\,607}$$$.

Example input:
2
5000 5000
5000 5000

Example output:
5927

Example input:
2
2500 6000
3000 4000

Example output:
24812

Editorial:
Let $$$l_1, l_2, \ldots, l_{2n+2}$$$ denote the $$$2n+2$$$ possible lines that can be formed. Let $$$L_i$$$ denote the event that line $$$l_i$$$ is formed, and $$$\overline{L_i}$$$ denote the event that line $$$l_i$$$ is not formed (i.e., $$$P(L_i) + P(\overline{L_i}) = 1$$$).
Let's find the probability that our table is not winning. It is equal to $$$P(\overline{L_1} \cap \overline{L_2} \cap \ldots \cap \overline{L_{2n+2}})$$$.
Note that the following two statements are true:
• $$$P(\overline{L_1} \cap \overline{L_2} \cap \ldots \cap \overline{L_{2n+2}}) + P(L_1 \cap \overline{L_2} \cap \ldots \cap \overline{L_{2n+2}}) = P(\overline{L_2} \cap \ldots \cap \overline{L_{2n+2}})$$$;
• $$$P(L_1 \cap \overline{L_2} \cap \ldots \cap \overline{L_{2n+2}}) = P(\overline{L_2} \cap \ldots \cap \overline{L_{2n+2}} | L_1) \cdot P(L_1)$$$.
The first one follows from the law of total probability, and the second one follows from the definition of conditional probability.
These two statements combined allow us to use the following formula:
We can apply this formula recursively. Specifically, we can make a function $$$f(i, S)$$$, where $$$S = \{s_1, s_2, \ldots, s_k\}$$$ is a subset of $$$\{1, 2, \ldots, i-1\}$$$, which calculates $$$P(\overline{L_i} \cap \overline{L_{i+1}} \cap \ldots \cap \overline{L_{2n+2}} | L_{s_1} \cap \ldots \cap L_{s_k})$$$. For $$$i = 2n+3$$$, $$$f(i, S) = 1$$$, and for $$$i \le 2n+2$$$ we can generalize the formula above as follows:
Here, $$$P(L_i | L_{s_1} \cap \ldots \cap L_{s_k})$$$ is the probability that line $$$l_i$$$ is formed given that lines $$$l_{s_1}, \ldots, l_{s_k}$$$ are formed. This is equal to the product of probabilities of all cells belonging to $$$l_i$$$ which do not belong to any of $$$l_{s_1}, \ldots, l_{s_k}$$$.
The answer to the problem, i.e. the probability that our table is winning, is $$$1 - f(1, \{\})$$$.
This allows us to implement an $$$O(2^{2n} \cdot n)$$$ solution, which is too slow. In fact, this solution is equivalent to applying inclusion-exclusion principle.
To optimize this solution, note that once it becomes easy to calculate $$$f(i, S)$$$, we don't have to make any more recursive calls. Why would it become easy to calculate $$$f(i, S)$$$ though?
Let's order the lines in such a way that $$$l_{n+3}, l_{n+4}, \ldots, l_{2n+2}$$$ are the horizontal lines of the table. Consider a call of the form $$$f(n + 3, S)$$$. This call is basically asking: "what is the probability that none of lines $$$l_{n+3}, l_{n+4}, \ldots, l_{2n+2}$$$ are formed, given that lines $$$l_{s_1}, \ldots, L_{s_k}$$$ are formed?".
Note that the horizontal lines are independent, and we can actually answer this question in $$$O(n^2)$$$. Specifically, for any horizontal line, the probability that it is not formed is $$$1$$$ minus the product of probabilities of all its cells not belonging to any of $$$l_{s_1}, \ldots, l_{s_k}$$$. The overall value of $$$f(n + 3, S)$$$ is the product of probabilities for individual horizontal lines.
This way, we have built an $$$O(2^n \cdot n^2)$$$ solution. This might be fast enough depending on your implementation, but there are at least two ways to optimize it to $$$O(2^n \cdot n)$$$:
• The first way is to maintain the products of probabilities of untouched cells for horizontal lines on the fly. For simplicity, assume that $$$l_1$$$ and $$$l_2$$$ are the diagonal lines. For each $$$i = 3, 4, \ldots, n+2$$$, after we process (vertical) line $$$l_i$$$, we can update the products for all horizontal lines with the cells of $$$l_i$$$ (in $$$O(n)$$$), make a recursive call, and roll back the updates (in $$$O(n)$$$ again). Once we get to $$$i = n + 3$$$, instead of going through every cell of the table in $$$O(n^2)$$$, we can just multiply $$$n$$$ horizontal line products in $$$O(n)$$$.
• The second way is to define $$$g(i, mask)$$$ ($$$1 \le i \le n$$$; $$$mask$$$ is a bitmask of size $$$n$$$) to be the product of $$$a_{i, j}$$$ over all $$$j$$$ belonging to $$$mask$$$. All values of $$$g$$$ can be calculated in $$$O(2^n \cdot n)$$$ using dynamic programming: $$$g(i, 0) = 1$$$, and $$$g(i, mask) = g(i, mask \oplus 2^j) \cdot a_{i, j}$$$, where $$$j$$$ is any bit set in $$$mask$$$. When we arrive at a $$$f(n + 3, S)$$$ call, for each of the $$$n$$$ horizontal lines, instead of going through its cells, we can construct the mask of cells the values in which we want to multiply, and use the corresponding value of $$$g$$$ in $$$O(1)$$$.