No.1720 Division Permutation
タグ : / 解いたユーザー数 8
作問者 :
nok0
/ テスター :
zkou
👑 
ygussany
問題文
数列 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。