問題一覧 > 通常問題

No.1720 Division Permutation

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 6
作問者 : nok0nok0 / テスター : zkouzkou 👑 ygussanyygussany
2 ProblemId : 6961 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-17 19:24:25

問題文

数列 $A$ を昇順に並び替えると隣接する要素の差がすべて $1$ となるとき、 $A$ を美しい数列と呼びます。例えば、 $(5,2,4,3,7,6)$ や $(1,2,3)$ や $(7)$ は美しい数列であり、 $(1,3,5,7)$ や $(2,3,4,5,7)$ は美しい数列ではありません。

長さ $N$ の $(1,2,\dots,N)$ を並び替えた順列 $P$ が与えられます。

順列 $P$ を以下の条件全てを満たすように $X$ 個の連続部分列 $B_1,B_2,\dots,B_X$ に分割します。

  • $B_1,B_2,\dots,B_X$ はいずれも $P$ の空でない連続部分列であり、かつ美しい数列である。
  • $B_1,B_2,\dots,B_X$ をこの順序で連結すると $P$ になる。

$X=1,2,\dots,K$ それぞれについて、条件を満たす分割の個数を $\bmod 998244353$ で求めてください。

制約

  • 入力は全て整数である。
  • $1 \le N \le 2 \times 10^5$
  • $1 \le K \le \mathrm{min}(N,$ $10$$)$
  • $P$ は $(1,2,\dots,N)$ を並び替えて得られる順列である。

入力

$N$ $K$
$P_1$ $P_2$ $\dots$ $P_N$

出力

$i\ (1\le i \le K)$ 行目に $X=i$ のときの答えを出力してください。

サンプル

サンプル1
入力
4 2
1 3 2 4
出力
1
2

$X=1$ のとき、 $(1,3,2,4)$ という分割が条件を満たします。

$X=2$ のとき、 $(1,3,2),(4)$ という分割と $(1),(3,2,4)$ という分割が条件を満たします。

サンプル2
入力
5 3
1 2 3 4 5
出力
1
4
6

非空な $X=1,2,3$ 個の連続部分列への分割全てが条件を満たします。

サンプル3
入力
10 10
1 3 2 4 5 8 9 7 6 10
出力
1
5
10
13
16
17
14
9
4
1

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