問題一覧 > 通常問題

No.1989 Pairing Multiset

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

問題文

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

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

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

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

    入力

    N  MN\ \ M

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

    • 出力

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

    サンプル

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

    各要素が 00 以上 11 以下の整数からなる要素数 44 の多重集合 SS は以下の 55 通りあります。

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

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

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

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

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

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

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