No.2068 Restricted Permutation
タグ : / 解いたユーザー数 32
作問者 :
遭難者
/ テスター :
SSRS
👑 
ygussany
とりゐ
問題文
長さ $N$ の順列 $P$ に対し $f(P)$ を $P$ より辞書順で先に来るような長さ $N$ の順列の個数と定義します。
長さ $N$ の順列 $P$ であって $P_K=X$ を満たすものは $(N-1)!$ 通りありますが、それらに対し $f(P)$ を計算したときのその総和を求めてください。
ただし、求める総和は非常に大きくなる可能性があるので $998244353$ で割った余りを出力してください。
▶長さ $N$ の順列とは
$(1,2,\ldots,N)$ を並び替えたものを指します。
▶辞書順で先に来るとは
長さ $N$ の順列 $P,Q$ に対し $P$ が $Q$ より先に来るとは、 $P_i\neq Q_i$ を満たす $i$ が存在し、そのような $i$ の中で最小のものを $j$ とした時に $P_j < Q_j$ であることを指します。
入力
$N\ K\ X$
出力
長さ $N$ の順列 $P$ で $P_K=X$ を満たすもの全てに対し $f(P)$ を計算した時のその総和を $998244353$ で割った余りを出力してください。
サンプル
サンプル1
入力
3 2 1
出力
6
条件を満たす $P$ は $P=(2,1,3),(3,1,2)$ で、それぞれに対して $f(P)=2,4$ です。したがって、これらの総和である $6$ を出力してください。
サンプル2
入力
4 4 4
出力
42
サンプル3
入力
100 1 3
出力
967152772
$998244353$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。