問題一覧 > 通常問題

No.1482 Swap Many Permutations

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 11
作問者 : nok0nok0 / テスター : tatyamtatyam 👑 fairy_lettucefairy_lettuce ygussanyygussany PCTprobabilityPCTprobability
3 ProblemId : 5956 / 出題時の順位表
問題文最終更新日: 2021-04-01 23:20:51

定義

この問題では、$0, 1, \dots, M-1$ を並び替えた数列 $P=(P_1,P_2,\dots,P_M)$ が $0$ 以上 $M-1$ 以下の整数 $x$ と $1$ 以上 $M-1$ 以下の整数 $y$ を用いて以下の漸化式で表せるとき、数列 $P$ を 初項 $x$ 公差 $y$ の等差順列、もしくは単に等差順列と呼びます。

$ P_{i} = \begin{cases} x & (i=1) \\ \left(P_{i-1} + y\right) \bmod M & (\mathrm{otherwise}) \end{cases} $

問題文

正整数 $N$, 素数 $M$, 長さ $N$ の数列 $B = (B_1,B_2,\dots,B_N), C = (C_1,C_2,\dots,C_N)$ が与えられます。

$K=1,2,\dots,N$ に対して以下の問題を解いてください。

問題

    長さ $M$ の順列が $K$ 個あります。 $i$ 番目の順列を $A_i = (A_{i,1},A_{i,2},\dots,A_{i,M})$ で表すとし、 はじめ $A_i$ は初項 $B_i$ 公差 $C_i$ の等差順列です。

    あなたは以下の操作を $0$ 回以上任意の回数行うことが出来ます。

    • $1\le x < y \le K$ なる整数 $x,y$ と $1\le i < j \le M$ なる整数 $i,j$ を選択する。 $A_{x,i}$ と $A_{x,j}$ を入れ替え、 $A_{y,i}$ と $A_{y,j}$ を入れ替える。

    操作を $0$ 回以上行った後の順列 $A_1,A_2,\dots,A_K$ の状態のうち、以下の条件を満たすものの個数を $\bmod998244353$ で求めてください。

    条件
    • 順列 $A_1,A_2,\dots,A_K$ は全て等差順列であり、互いに相異なる。

制約

  • 入力は全て整数である。
  • $2\le N \le 10^5$
  • $2\le M \le 40009\ $(素数)
  • $M$ は素数である。
  • $0\le B_i < M$
  • $1\le C_i < M$

入力

$N\ M$
$B_1\ C_1$
$B_2\ C_2$
$\vdots$
$B_N\ C_N$

出力

出力は $N$ 行からなる。

$i(1\le i\le N)$ 行目には $K = i$ の時の問題の答えを出力せよ。

サンプル

サンプル1
入力
3 3
0 1
2 1
0 2
出力
1
6
60

$A_1 = (0,1,2), A_2 =(2,0,1),A_3 =(0,2,1)$ です。

$K =1$ のとき、操作は一度も行えないので答えは $1$ です。

$K=2$ のとき、例えば $(x,y,i,j) = (1,2,1,2)$ として一度操作を行うことで、$A_1=(1,0,2),A_2=(0,2,1)$ という状態を生成できます。 $A_1$ は初項 $1$ 公差 $2$ の等差順列、 $A_2$ は初項 $0$ 公差 $2$ の等差順列であり、これは互いに相異なるので求める状態の一つです。

サンプル2
入力
7 29
3 1
4 1
5 9
2 6
5 3
5 8
9 7
出力
1
812
266705460
144923472
504663788
985419457
834752953

$\bmod 998244353$ で出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。