問題一覧 > 通常問題

No.1989 Pairing Multiset

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 69
作問者 : milkcoffee / テスター : tokusakurai riano
お気に入りにしたユーザー ProblemId : 7879 / 自分の提出
問題文最終更新日: 2022-05-03 20:43:17
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 349 (順位表) の他の問題:

Problem Statement

For a multiset $S$ of size $2N$ whose elements are all integers between $0$ and $M$, inclusive, define $f(S)$ as follows.

  • Divide the $2N$ integers into $N$ pairs of integers, and for each pair compute the absolute difference of its $2$ elements. The value is the minimum possible sum of the $N$ absolute differences obtained.

  • For example, when $S= \{ 0,1,7,8 \}$, dividing it into the $2$ pairs $(0,1)$, $(7,8)$ gives a sum of absolute differences of $|0-1|+|7-8|=2$.
    It cannot be made any smaller, so $f(S)=2$.

    Find the sum of $f(S)$ over all possible multisets, modulo $998244353$.

    Input

    $N\ \ M$
    

  • $1 \leq N \leq 10^6$
  • $1 \leq M \leq 10^9$
  • All inputs are integers.
  • Output

    Output, as an integer, the sum of $f(S)$ over all multisets, modulo $998244353$.

    Sample

    Sample 1
    Input
    2 1
    
    Output
    2
    

    There are the following $5$ multisets $S$ of size $4$ whose elements are integers between $0$ and $1$, inclusive.

    When $S= \{0,0,0,0 \}$, $f(S)=0$
    When $S= \{0,0,0,1 \}$, $f(S)=1$
    When $S= \{0,0,1,1 \}$, $f(S)=0$
    When $S= \{0,1,1,1 \}$, $f(S)=1$
    When $S= \{1,1,1,1 \}$, $f(S)=0$

    The answer is their sum, $2$.

    Sample 2
    Input
    123321 101010101
    
    Output
    831707051
    

    Note that you must output the remainder modulo $998244353$.

    Sample 3
    Input
    998244 998244353
    
    Output
    0
    

    Note that the value to output may be $0$.

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