問題一覧 > 通常問題

No.1482 Swap Many Permutations

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 18
作問者 : nok0 / テスター : tatyam fairy_lettuce ygussany PCTprobability
お気に入りにしたユーザー ProblemId : 5956 / 自分の提出
問題文最終更新日: 2021-04-01 23:20:51
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 291 (順位表) の他の問題:

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

    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.

    • 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}$.

    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$.

    Condition
    • The permutations $A_1,A_2,\dots,A_K$ are all arithmetic permutations and are pairwise distinct.

Constraints

  • 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もしくは右上の雲マークをクリックしてアカウントを作成してください。