| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 6 | 6 | 6 | 100.000% |
A certain aspiring musician K loves going for shabu-shabu! Recently, she’s been to $N$ shabushabu restaurants, numbered 1,ドル 2, \dots , N,ドル following the following algorithm:
It is guaranteed that $\bigcup^N_{i=1} R_i = \{2, \dots , N\}$ and $R_i ∩ R_j = ∅$ for $i \ne j,ドル that is, every restaurant, other than the first, will be recommended by exactly one other restaurant.
Once K finishes her list, K’s delinquent friend H decides to play a prank on her! She replaces the array $A_0, \dots , A_{N−1}$ with another array $B_0, \dots , B_{N−1}$! K thinks that this new array $B_i$ might just be a cyclic shift of her array, so she asks you to determine all possible 0ドル ≤ k < N$ such that $A_i = B_{(i+k) \bmod N},ドル for all 0ドル ≤ i < N$ and any valid output of her algorithm $A_0, \dots , A_{N−1}$.
Furthermore, K will then perform $Q$ operations, where for the $i$-th operation, she swaps $B_{x_i},ドル $B_{y_i}$ and asks you to do the same on the new array. Can you help K see through her friend’s prank?
The first line of input will contain two integers, $N$ (1ドル ≤ N ≤ 500,円 000$) and $Q$ (0ドル ≤ Q ≤ 300,円 000$).
The next line of input will contain $N$ space-separated non-negative integers, $B_0, B_1, \dots , B_{N−1}$ (0ドル ≤ B_i < N$), the initial sequence.
The $i$-th of the next $Q$ lines of input will contain two integers each, $x_i$ and $y_i$ (0ドル ≤ x_i , y_i < N$ and $x_i \ne y_i$), indicating you are to swap $B_{x_i}$ with $B_{y_i}$ .
For each of the $Q + 1$ arrays (including the initial array $B_0, \dots , B_{N−1}$), let $S = \{k_1, \dots , k_m\}$ denote the set of integers 0ドル ≤ k_j < N$ such that there exists a valid output $A_0, \dots , A_{N−1}$ of K’s algorithm such that $A_i = B_{(i+k_j ) \bmod N}$ for all 0ドル ≤ i < N$. Output, on a single line, the integers $m$ and $\sum^m_{i=1} k_i \pmod {998,円 244,円 353},ドル separated by a space.
In particular, if $S = ∅,ドル your output should be 0 0.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | 1ドル ≤ N ≤ 8,ドル $Q = 0$ |
| 2 | 7 | 1ドル ≤ N ≤ 5,円 000,ドル $Q = 0$ |
| 3 | 10 | 1ドル ≤ N ≤ 500,円 000,ドル $Q = 0$ |
| 4 | 5 | 1ドル ≤ N ≤ 500,円 000,ドル 0ドル ≤ Q ≤ 300,円 000$ |
5 3 1 2 0 0 1 0 2 1 3 3 2
1 4 1 1 1 2 1 2
The array $A$ is $[1, 1, 2, 0, 0]$; it can be shown this is the only valid output of K’s algorithm that corresponds to the array $B = [1, 2, 0, 0, 1]$. One input for K’s algorithm that yields this array $A$ is: \begin{align*}R_1 &= \{2\} \\ R_2 &= \{3\} \\R_3 &= \{4, 5\}\\ R_4 &= ∅ \\ R_5 &= ∅\text{.}\end{align*}
After swapping $B_0$ and $B_2,ドル we get the array \begin{align*}B = [0, 2, 1, 0, 1]\text{.}\end{align*}
It can be shown the only valid output of K’s algorithm that corresponds to this is \begin{align*}A = [2, 1, 0, 1, 0]\text{.}\end{align*}
One possible input to K’s algorithm that yields this array $A$ is \begin{align*}R_1 &= \{2, 3\} \\ R_2 &= \{4\}\\ R_3 &= ∅ \\ R_4 &= \{5\} \\ R_5 &= ∅\text{.}\end{align*}