Two Options#13011

Two Options (Editorial)

Author:

Roman Bilyi

Prepared by:

Yarema Stiahar

Solved by:

First to solve:

2Popici1Arici

Let’s assume some value there are at least 2 triplets with that value (a_1, b_1, v) and (a_2, b_2, v). If all values a_1, b_1, a_2, b_2 are distinct, the answer is 0. WLOG, a_1=b_2=x, then should hold p_x=v. So we can find positions of all values that appear more than once(or the answer is 0). After that, while we have triplets (i, j, v) such that either position or is used, we can set value to another one. After that we have left only triplets with unique values and no positions solved.

For each triplet (a, b, v) let’s create undirected edge between nodes and . We must assign each value to one of its possible nodes such that each node receives at most one value (some nodes may receive values that weren’t present in any triplet). Let’s say that we must direct edges such that for each node at most one edge points towards it. Note that actual values don’t matter.

We decompose the graph into connected components. Let a component have V_c vertices and E_c edges. Since each vertex can hold only one value, we must have E_c \le V_c. If E_c > V_c for any component, the answer is .

We have the following cases:

Let be the number of values that were completely unconstrained (not presented in any triplet). These values will fill the positions left empty by the tree components. The total number of good permutations is:

\text{Ans} = \left( \prod_{\text{components } c} \text{Ways}(c) \right) \times K! \pmod{10^9 + 7}

Complexity: O(n+m).