#P12969. [CCO 2025] Restaurant Recommendation Rescue

    ID: 12771 Type: RemoteJudge 2000ms 2048MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2025CCO(加拿大)

[CCO 2025] Restaurant Recommendation Rescue

题目描述

A certain aspiring musician K loves going for shabu-shabu! Recently, she's been to NN shabu-shabu restaurants, numbered 1,2,,N1, 2, \ldots, N, following the following algorithm:

  1. K keeps an ordered list of recommendations, starting with restaurant 1.
  2. On the ii-th day, she visits the next recommended restaurant on her list, which recommends her restaurants Ri={ri,1,,ri,li}R_i = \{r_{i,1}, \ldots, r_{i,l_i}\}.
  3. K appends RiR_i to her list of restaurants to visit.
  4. K repeats steps 2-4 until she runs out of recommended restaurants.
  5. K writes down the array A0,,AN1A_0, \ldots, A_{N-1}, where AiA_i equals the number of restaurants she was recommended on the (i+1)(i+1)-th day. That is, Ai=Ri+1A_i = |R_{i+1}|.

It is guaranteed that i=1NRi={2,,N}\bigcup_{i=1}^{N} R_i = \{2, \ldots, N\} and RiRj=R_i \cap R_j = \emptyset for iji \neq 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 A0,,AN1A_0, \ldots, A_{N-1} with another array B0,,BN1B_0, \ldots, B_{N-1}! K thinks that this new array BiB_i might just be a cyclic shift of her array, so she asks you to determine all possible 0k<N0 \leq k < N such that Ai=B(i+k)modNA_i = B_{(i+k) \bmod N}, for all 0i<N0 \leq i < N and any valid output of her algorithm A0,,AN1A_0, \ldots, A_{N-1}.

Furthermore, K will then perform QQ operations, where for the ii-th operation, she swaps Bxi,ByiB_{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, NN (1N5000001 \leq N \leq 500\,000) and QQ (0Q3000000 \leq Q \leq 300\,000).

The next line of input will contain NN space-separated non-negative integers, B0,B1,,BN1B_0, B_1, \ldots, B_{N-1} (0Bi<N0 \leq B_i < N), the initial sequence.

The ii-th of the next QQ lines of input will contain two integers each, xix_i and yiy_i (0xi,yi<N0 \leq x_i, y_i < N and xiyix_i \neq y_i), indicating you are to swap BxiB_{x_i} with ByiB_{y_i}.

输出格式

For each of the Q+1Q + 1 arrays (including the initial array B0,,BN1B_0, \ldots, B_{N-1}), let S={k1,,km}S = \{k_1, \ldots, k_m\} denote the set of integers 0kj<N0 \leq k_j < N such that there exists a valid output A0,,AN1A_0, \ldots, A_{N-1} of K's algorithm such that Ai=B(i+kj)modNA_i = B_{(i + k_j) \bmod N} for all 0i<N0 \leq i < N. Output, on a single line, the integers mm and i=1mki(mod998244353)\sum_{i=1}^{m} k_i \pmod{998\,244\,353}, separated by a space.

In particular, if S=S = \emptyset, your output should be 0 0.

5 3
1 2 0 0 1
0 2
1 3
3 2
1 4
1 1
1 2
1 2

提示

Sample 1 Explanation

The array AA is [1,1,2,0,0][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]B = [1, 2, 0, 0, 1]. One input for K's algorithm that yields this array AA is:

$\begin{aligned} R_1 &= \{2\} \\ R_2 &= \{3\} \\ R_3 &= \{4, 5\} \\ R_4 &= \varnothing \\ R_5 &= \varnothing. \end{aligned}$

After swapping B0B_0 and B2B_2, we get the array

B=[0,2,1,0,1].B = [0, 2, 1, 0, 1].

It can be shown the only valid output of K's algorithm that corresponds to this is

A=[2,1,0,1,0].A = [2, 1, 0, 1, 0].

One possible input to K's algorithm that yields this array AA is

$\begin{aligned} R_1 &= \{2, 3\} \\ R_2 &= \{4\} \\ R_3 &= \varnothing \\ R_4 &= \{5\} \\ R_5 &= \varnothing. \end{aligned}$

The following table shows how the available 2525 marks are distributed:

Marks Awarded Bounds on NN Bounds on QQ
3 marks 1N81 \leq N \leq 8 Q=0Q = 0
7 marks 1N50001 \leq N \leq 5\,000
10 marks 1N5000001 \leq N \leq 500\,000
5 marks 0Q3000000 \leq Q \leq 300\,000