No.1482 Swap Many Permutations
タグ : / 解いたユーザー数 18
作問者 :
nok0
/ テスター :
tatyam
PCTprobability
Definition
In this problem, when a sequence $P=(P_1,P_2,\dots,P_M)$ obtained by rearranging $0, 1, \dots, M-1$ can be expressed by the following recurrence using an integer $x$ between $0$ and $M-1$, inclusive, and an integer $y$ between $1$ and $M-1$, inclusive, the sequence $P$ is called an arithmetic permutation with first term $x$ and common difference $y$, or simply an arithmetic permutation.
$ P_{i} = \begin{cases} x & (i=1) \\ \left(P_{i-1} + y\right) \bmod M & (\mathrm{otherwise}) \end{cases} $
Problem Statement
You are given a positive integer $N$, a prime number $M$, and sequences $B = (B_1,B_2,\dots,B_N), C = (C_1,C_2,\dots,C_N)$ of length $N$.
Solve the following problem for each of $K=1,2,\dots,N$.
Problem
- Choose integers $x,y$ such that $1\le x < y \le K$ and integers $i,j$ such that $1\le i < j \le M$. Swap $A_{x,i}$ and $A_{x,j}$, and swap $A_{y,i}$ and $A_{y,j}$.
- The permutations $A_1,A_2,\dots,A_K$ are all arithmetic permutations and are pairwise distinct.
There are $K$ permutations of length $M$. The $i$-th permutation is denoted by $A_i = (A_{i,1},A_{i,2},\dots,A_{i,M})$, and initially $A_i$ is the arithmetic permutation with first term $B_i$ and common difference $C_i$.
You may perform the following operation any number of times, possibly $0$ times.
Among the states of the permutations $A_1,A_2,\dots,A_K$ after performing the operation $0$ or more times, find the number of those satisfying the following condition, $\bmod998244353$.
ConditionConstraints
- All input values are integers.
- $2\le N \le 10^5$
- $2\le M \le 40009\ $(prime)
- $M$ is a prime number.
- $0\le B_i < M$
- $1\le C_i < M$
Input
$N\ M$ $B_1\ C_1$ $B_2\ C_2$ $\vdots$ $B_N\ C_N$
Output
The output consists of $N$ lines.
On the $i(1\le i\le N)$-th line, print the answer to the problem for $K = i$.
Sample
Sample 1
Input
3 3 0 1 2 1 0 2
Output
1 6 60
We have $A_1 = (0,1,2), A_2 =(2,0,1),A_3 =(0,2,1)$.
When $K =1$, no operation can be performed, so the answer is $1$.
When $K=2$, for example, by performing the operation once with $(x,y,i,j) = (1,2,1,2)$, the state $A_1=(1,0,2),A_2=(0,2,1)$ can be produced. $A_1$ is the arithmetic permutation with first term $1$ and common difference $2$, and $A_2$ is the arithmetic permutation with first term $0$ and common difference $2$. These are distinct from each other, so this is one of the states to be counted.
Sample 2
Input
7 29 3 1 4 1 5 9 2 6 5 3 5 8 9 7
Output
1 812 266705460 144923472 504663788 985419457 834752953
Print the answers $\bmod 998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。