No.2613 Sum of Combination
タグ : / 解いたユーザー数 35
作問者 :
蜜蜂
/ テスター :
Mitarushi
問題文
整数 $N$ と素数 $P$ が与えられます。
$0$ 以上 $N$ 以下の全ての整数 $R$ に対して、 ${}_{N}\mathrm{C}_{R}$ を $P$ で割った余りを足し合わせることで得られる数を $998244353$ で割った余りを求めて下さい。
なお、 ${}_{N}\mathrm{C}_{R}$ は $N$ 個のものから $R$ 個のものを選ぶ場合の数を指します。すなわち $0! = 1$ として $\frac{N!}{R!\left( N - R \right)!}$ です。
すなわち、以下の値を出力してください。ここで $A \ \mathrm{mod}\ B$ を $A$ を $B$ で割った余りとします。
$
\left( \sum_{R=0}^{N} \left( {}_{N}\mathrm{C}_{R}\ \mathrm{mod}\ P \right) \right) \mathrm{mod}\ 998244353
$
入力
$N\ \ P$
- $1 \leq N \leq 10^{18}$
- $2 \leq P \leq 2 \times 10^5$
- $P$ は素数
- 入力は全て整数
出力
$ \left( \sum_{R=0}^{N} \left( {}_{N}\mathrm{C}_{R}\ \mathrm{mod}\ P \right) \right) \mathrm{mod}\ 998244353 $ を出力し、最後に改行してください。
サンプル
サンプル1
入力
5 3
出力
8
${}_{N}\mathrm{C}_{R}$ は $R$ が $0,1,2,3,4,5$ の時にそれぞれ $1,5,10,10,5,1$ となります。
これを $3$ で割った余りはそれぞれ $1,2,1,1,2,1$ です。
これらを足し合わせて得られる数は $8$ であり、これを $998244353$ で割った余りは $8$ となります。
サンプル2
入力
1 5
出力
2
${}_{N}\mathrm{C}_{R}$ は $R$ が $0,1$ の時にそれぞれ $1,1$ となります。
これを $5$ で割った余りはそれぞれ $1,1$ です。
これらを足し合わせて得られる数は $2$ であり、これを $998244353$ で割った余りは $2$ となります。
サンプル3
入力
223606797 7499
出力
779521711
$998244353$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。