No.2467 Sum of Product of Binomial Coefficients
問題文最終更新日: 2025-10-14 00:40:02
English (AI translation)
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
Problem Statement
You are given integers $N,K$. For a positive integer $k$, let $f(k)$ be the answer to the following problem.
- The sum of $\displaystyle \binom{N}{a_1} \times \binom{a_1}{a_2} \times \cdots \times \binom{a_{k-1}}{a_k}$ over all integer sequences $(a_1, a_2, \ldots, a_k)$ satisfying $N\geq a_1\geq a_2\geq \ldots \geq a_k \geq 0$
Find $\displaystyle \sum_{k=1}^K f(k)$ modulo $998244353$.
Solve $T$ test cases per $1$ input.
Here, $\displaystyle \binom{A}{B}$ denotes "the number of ways to choose $B$ items from $A$ items" (that is, the binomial coefficient).
Constraints
- All input values are integers
- $1\leq T\leq 10^5$
- $0\leq N\leq 10^9$
- $1\leq K\leq 2\times 10^5$
- The sum of $K$ over the test cases contained in $1$ input does not exceed $2\times 10^5$
Input
$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$
Each test case is given in the following format.
$N$ $K$
Output
Sample
Sample 1
Input
3 3 3 0 1 31415 92653
Output
99 1 276482222
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
だれ
akakimidori
りあん
tsutaj
beet
tute7627
SPD_9X2
nok0
momoyuu