問題一覧 > 通常問題

No.1621 Sequence Inversions

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 55
作問者 : だれだれ / テスター : nok0nok0 yuto1115yuto1115
2 ProblemId : 6712 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-21 19:10:57

問題文

$A_1,A_2,\cdots,A_N$ を並べ替えた列 $B_1,B_2,\cdots,B_N$ であって、$1\leq i\lt j\leq N$ かつ $B_i\gt B_j$ となる組 $(i, j)$ がちょうど $K$ 個であるものの個数を求めてください。

入力

$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

  • 入力はすべて整数
  • $2\leq N\leq 100$
  • $0\leq K\leq \frac{N(N-1)}{2}$
  • $1\leq A_i\leq 10^9$
  • 出力

    答えを一行に出力してください。

    答えは非常に大きくなることがあるので、$998244353$ で割った余りを出力してください。

    サンプル

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

    $(1,3,2,2),\ (2,1,3,2),\ (2,2,1,3)$ の $3$ つです。

    サンプル2
    入力
    2 1
    1 1
    
    出力
    0

    サンプル3
    入力
    20 100
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    
    出力
    295100981

    $998244353$ で割ったあまりを答えてください。

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