P10813 [MX-S2-T4] Swap

Original link: 。

Given $n, V$ and a sequence of length $m$: $(p_1, q_1), (p_2, q_2), \dots, (p_m, q_m)$. Find how many positive integer sequences $a$ of length $n$ satisfy that every element $a_i$ meets $1 \le a_i \le V$, and after performing the following operation in order for $k = 1, 2, \dots, m$, the sequence $a$ becomes non-decreasing: - If $a_{p_k} > a_{q_k}$, swap the values of $a_{p_k}$ and $a_{q_k}$. Output the answer modulo $10^9 + 7$.

The first line contains three integers $n, V, m$. The next $m$ lines each contain two integers $p_k, q_k$.

Output one integer, the result modulo $10^9 + 7$.

**Sample Explanation #1** For the first sample, there are $12$ valid sequences: $\{1,1,1\}$, $\{1,1,2\}$, $\{1,1,3\}$, $\{1,2,1\}$, $\{1,3,1\}$, $\{2,1,1\}$, $\{2,2,2\}$, $\{2,2,3\}$, $\{2,3,2\}$, $\{3,1,1\}$, $\{3,2,2\}$, $\{3,3,3\}$。 **Constraints** **This problem uses bundled testdata.** - Subtask 0 (8 pts): $n \le 6$, $V \le 8$, $m \le 50$. - Subtask 1 (31 pts): $n \le 8$. - Subtask 2 (37 pts): $n \le 15$. - Subtask 3 (24 pts): no special constraints. For all testdata, $1 \le n \le 18$, $1 \le V \le 10^9$, $1 \le m \le 500$, $1 \le p_k, q_k \le n$. Note that the relative order of $p_k$ and $q_k$ is not guaranteed, and the data may contain $p_k = q_k$. Translated by ChatGPT 5