問題一覧 > 通常問題

No.2613 Sum of Combination

レベル : / AI推定難易度 : 2250 / 実行時間制限 : 1ケース 4.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 35
作問者 : 蜜蜂 / テスター : Mitarushi
お気に入りにしたユーザー ProblemId : 6008 / 自分の提出
問題文最終更新日: 2024-01-19 17:53:10
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 415 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。