| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 343 | 182 | 99 | 57.895% |
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:
Sum of $N$ over all cases $\le 2\,000$.
Output how many such permutations $c$ described in the problem exist.
Modified constraints apply: $1 \le N \le 8;$ Sum of $N$ over all cases $\le 1\,000$.
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$.
Original constraints apply: $1 \le N \le 16;$ Sum of $N$ over all cases $\le 2\,000$.
1 4 1 2 3 4 2 3 1 4
3
There are $3$ such permutations:
\[[3,1,4,2] \qquad [3,4,2,1] \qquad [4,1,2,3]\]
You may have to use a type larger than a $32$-bit integer to prevent overflow in this problem.
University > 서강대학교 > CSE4152 문제해결프로그래밍실습 > 2024-2학기 기말고사 코딩 테스트 3번