No.1989 Pairing Multiset
タグ : / 解いたユーザー数 69
作問者 :
milkcoffee
/ テスター :
riano
Problem Statement
For a multiset $S$ of size $2N$ whose elements are all integers between $0$ and $M$, inclusive, define $f(S)$ as follows.
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$
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もしくは右上の雲マークをクリックしてアカウントを作成してください。