問題一覧 > 通常問題

No.2068 Restricted Permutation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 : 遭難者遭難者 / テスター : SSRSSSRS ygussanyygussany とりゐとりゐ
1 ProblemId : 8354 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-01 01:32:46

問題文

長さ $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$

  • $1\le N\le 2\times 10^5$
  • $1\le K\le N$
  • $1\le X\le N$
  • 入力は全て整数である。

    • 出力

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