33067번 - Double Derangement 서브태스크다국어

문제

You are given two permutations $a$ and $b,ドル each of length $N$ containing every integer in the range $[1,N]$. Your task is to construct a new permutation $c$ of length $N$ that contains every integer in the range $[1,N],ドル such that for every index $i$ (1ドル$-indexed), the following condition is satisfied:

\[c_i \neq a_i \quad \text{and} \quad c_i \neq b_i.\]

In other words, for no index $i$ can $c_i$ be equal to $a_i$ or $b_i$​.

Given the permutations $a$ and $b,ドル determine how many such permutations $c$ exist.

입력

The first line of input contains a single integer $T,ドル denoting the number of test cases.

For each test case, the input is as follows:

• The first line of each test case contains a single integer, $N,ドル denoting the length of the permutations. (1ドル \le N \le 16$)
• The next line contains $N$ space-separated integers, denoting the permutation $a$. Here, the $i$-th integer denotes $a_i$​. (1ドル \le a_i \le N;$ $i \ne j \rightarrow a_i \ne a_j$​)
• The next line contains $N$ space-separated integers, denoting the permutation $b$. Here, the $i$-th integer denotes $b_i$​. (1ドル \le b_i \le N;$ $i \ne j \rightarrow b_i \ne b_j$)

Sum of $N$ over all cases $\le 2,000円$.

출력

Output how many such permutations $c$ described in the problem exist.

제한

서브태스크 1 (40점)

Modified constraints apply: 1ドル \le N \le 8;$ Sum of $N$ over all cases $\le 1,000円$.

서브태스크 2 (40점)

Modified constraints apply: 1ドル \le N \le 16;$ $\boldsymbol{\underline{a=b}},$ i.e., the permutation $a$ and $b$ is same for all indices 1ドル \le i \le N;$ Sum of $N$ over all cases $\le 2,000円$.

서브태스크 3 (20점)

Original constraints apply: 1ドル \le N \le 16;$ Sum of $N$ over all cases $\le 2,000円$.

노트

You may have to use a type larger than a 32ドル$-bit integer to prevent overflow in this problem.