34349번 - Splits 서브태스크다국어언어 제한함수 구현

For a permutation $p = p[0] p[1] p[2] \dots p[n − 1]$ of the numbers $1, 2, 3,\dots,n$ we define a split as a permutation $q$ which can be obtained by the following process:

1. Select two sets of numbers $A = \{ i_1 ,i_2 , \dots , i_k \}$ and $B = \{ j_1 , j_2 ,\dots , j_l \}$ such that $A ∩ B = ∅$, $A ∪ B = \{ 0, 1, 2, \dots ,n − 1 \}$, $i_1 < i_2 < \dots < i_k$ and $j_1 < j_2 < \dots < j_l$.
2. The permutation $q$ will be $q = p[i_1 ]p[i_2 ]\dots p[i_k ]p[j_1 ]p[j_2 ]\dots p[j_l ]$

Moreover, we define $S(p)$ to be the set of all splits of a permutation $p$.

You are given a number $n$ and a set $T$ of $m$ permutations of length $n$. Count how many permutations $p$ of length $n$ exist such that $T ⊆ S(p)$. Since this number can be large, find it modulo $998\, 244\, 353$.

You should implement the following procedure:

int solve(int n, int m, std::vector<std::vector<int>>& splits);

• $n$: the size of the permutation
• $m$: the number of splits
• $splits$: array containing $m$ pairwise distinct permutations, the elements of the set $T$, which is a subset of $S(p)$
• This procedure should return the number of possible permutations modulo $998\, 244\, 353$.
• This procedure is called exactly once for each test case.

• $1 ≤ n ≤ 300$
• $1 ≤ m ≤ 300$

Example 1

Consider the following call:

solve(3, 2, {{1, 2, 3}, {2, 1, 3}})

In this sample, the size of the permutation $p$ is $3$ and we are given $2$ splits:

• $1$ $2$ $3$
• $2$ $1$ $3$

The function call will return $4$ as there are only four permutations $p$ that can generate both of those splits:

• $1$ $2$ $3$
• $1$ $3$ $2$
• $2$ $1$ $3$
• $2$ $3$ $1$

The sample grader reads the input in the following format:

• line $1$: $n$ $m$
• line $2 + i$: $s[i][0]$ $s[i][1]$ $\dots$ $s[i][n − 1]$ for all $0 ≤ i < m$

and outputs the result of the call to solve with the corresponding parameters.

• sample-grader.cpp