No.2613 Sum of Combination
Problem Statement
You are given an integer $N$ and a prime $P$.
For every integer $R$ between $0$ and $N$, inclusive, take the remainder when ${}_{N}\mathrm{C}_{R}$ is divided by $P$, and add these remainders together. Find the remainder when the resulting number is divided by $998244353$.
Here, ${}_{N}\mathrm{C}_{R}$ denotes the number of ways to choose $R$ items from $N$ items. That is, it equals $\frac{N!}{R!\left( N - R \right)!}$, where $0! = 1$.
In other words, output the following value, where $A \ \mathrm{mod}\ B$ denotes the remainder when $A$ is divided by $B$.
$
\left( \sum_{R=0}^{N} \left( {}_{N}\mathrm{C}_{R}\ \mathrm{mod}\ P \right) \right) \mathrm{mod}\ 998244353
$
Input
$N\ \ P$
- $1 \leq N \leq 10^{18}$
- $2 \leq P \leq 2 \times 10^5$
- $P$ is a prime
- All input values are integers
Output
Output $ \left( \sum_{R=0}^{N} \left( {}_{N}\mathrm{C}_{R}\ \mathrm{mod}\ P \right) \right) \mathrm{mod}\ 998244353 $, followed by a newline.
Sample
Sample 1
Input
5 3
Output
8
For $R$ equal to $0,1,2,3,4,5$, ${}_{N}\mathrm{C}_{R}$ equals $1,5,10,10,5,1$, respectively.
Their remainders when divided by $3$ are $1,2,1,1,2,1$, respectively.
The sum of these is $8$, and its remainder when divided by $998244353$ is $8$.
Sample 2
Input
1 5
Output
2
For $R$ equal to $0,1$, ${}_{N}\mathrm{C}_{R}$ equals $1,1$, respectively.
Their remainders when divided by $5$ are $1,1$, respectively.
The sum of these is $2$, and its remainder when divided by $998244353$ is $2$.
Sample 3
Input
223606797 7499
Output
779521711
Output the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
蜜蜂