問題一覧 > 通常問題

No.2467 Sum of Product of Binomial Coefficients

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : だれだれ / テスター : akakimidoriakakimidori りあんりあん tsutajtsutaj beetbeet 👑 tute7627tute7627 👑 SPD_9X2SPD_9X2 nok0nok0 👑 rin204rin204 momoyuumomoyuu KKT89KKT89
1 ProblemId : 9690 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-17 20:15:53

問題文

整数 $N,K$ が与えられます。正整数 $k$ に対し、次の問題の答えを $f(k)$ とします。

  • $N\geq a_1\geq a_2\geq \ldots \geq a_k \geq 0$ を満たす全ての整数列 $(a_1, a_2, \ldots, a_k)$ に対する $\displaystyle \binom{N}{a_1} \times \binom{a_1}{a_2} \times \cdots \times \binom{a_{k-1}}{a_k}$ の総和

    • $\displaystyle \sum_{k=1}^K f(k)$ を $998244353$ で割ったあまりを求めてください。

    $1$ つの入力につき $T$ 個のテストケースについて解いてください。

    ただし $\displaystyle \binom{A}{B}$ は「$A$ 個のものから $B$ 個のものを選び出す場合の数」（つまり二項係数）を表します。

    制約

  • 入力はすべて整数
  • $1\leq T\leq 10^5$
  • $0\leq N\leq 10^9$
  • $1\leq K\leq 2\times 10^5$
  • $1$ つの入力に含まれるテストケースについて、$K$ の総和は $2\times 10^5$ を超えない

    • 入力

    $T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

    各テストケースは以下の形式で与えられる。

    $N$ $K$

    出力

    サンプル

    サンプル1
    入力
    3
3 3
0 1
31415 92653
    出力
    99
1
276482222

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。