問題一覧 > 通常問題

No.1989 Pairing Multiset

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 63
作問者 : milkcoffeemilkcoffee / テスター : tokusakuraitokusakurai rianoriano
7 ProblemId : 7879 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-03 20:43:17

問題文

各要素が $0$ 以上 $M$ 以下の整数である要素数 $2N$ の多重集合 $S$ に対して、$f(S)$ を以下のように定義します。

  • $2N$ 個の整数を $N$ 個の整数の組に分け、組ごとに $2$ つの要素の差の絶対値を求める。求めた $N$ 個の差の絶対値の合計として考えうる最小値。

    • 例えば、 $S= \{ 0,1,7,8 \}$ のとき、$(0,1)$, $(7,8)$ という $2$ つの組に分ければ、各組の差の絶対値の合計は $|0-1|+|7-8|=2$ となります。
    これ以上小さくすることはできないため、$f(S)=2$ となります。

    考えうる全ての多重集合に対する $f(S)$ の和を $998244353$ で割った余りを求めてください。

    入力

    $N\ \ M$

  • $1 \leq N \leq 10^6$
  • $1 \leq M \leq 10^9$
  • 入力は全て整数である

    • 出力

    全ての多重集合に対する $f(S)$ の和を $998244353$ で割った余りを整数で出力してください。

    サンプル

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

    各要素が $0$ 以上 $1$ 以下の整数からなる要素数 $4$ の多重集合 $S$ は以下の $5$ 通りあります。

    $S= \{0,0,0,0 \}$ であるとき、 $f(S)=0$
    $S= \{0,0,0,1 \}$ であるとき、 $f(S)=1$
    $S= \{0,0,1,1 \}$ であるとき、 $f(S)=0$
    $S= \{0,1,1,1 \}$ であるとき、 $f(S)=1$
    $S= \{1,1,1,1 \}$ であるとき、 $f(S)=0$

    これらの和である $2$ が答えです。

    サンプル2
    入力
    123321 101010101
    出力
    831707051

    $998244353$ で割った余りを出力することに注意してください。

    サンプル3
    入力
    998244 998244353
    出力
    0

    出力するべき値が $0$ になる場合があることに注意してください。

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