問題一覧 > 通常問題

No.2068 Restricted Permutation

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

問題文

長さ NN の順列 PP に対し f(P)f(P) を PP より辞書順で先に来るような長さ NN の順列の個数と定義します。
長さ NN の順列 PP であって PK=XP_K=X を満たすものは (N−1)!(N-1)! 通りありますが、それらに対し f(P)f(P) を計算したときのその総和を求めてください。
ただし、求める総和は非常に大きくなる可能性があるので 998244353998244353 で割った余りを出力してください。

▶長さ NN の順列とは

(1,2,…,N)(1,2,\ldots,N) を並び替えたものを指します。

▶辞書順で先に来るとは

長さ NN の順列 P,QP,Q に対し PP が QQ より先に来るとは、 Pi≠QiP_i\neq Q_i を満たす ii が存在し、そのような ii の中で最小のものを jj とした時に Pj<QjP_j < Q_j であることを指します。

入力

N K XN\ K\ X

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

    • 出力

    長さ NN の順列 PP で PK=XP_K=X を満たすもの全てに対し f(P)f(P) を計算した時のその総和を 998244353998244353 で割った余りを出力してください。

    サンプル

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

    条件を満たす PP は P=(2,1,3),(3,1,2)P=(2,1,3),(3,1,2) で、それぞれに対して f(P)=2,4f(P)=2,4 です。したがって、これらの総和である 66 を出力してください。

    サンプル2
    入力
    4 4 4
    出力
    42

    サンプル3
    入力
    100 1 3
    出力
    967152772

    998244353998244353 で割った余りを出力してください。

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