問題一覧 > 教育的問題

No.2130 Counting Ways to Distribute mod 998244353

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 118
作問者 : 👑 p-adic / テスター : 👑 箱星 taiga0629kyopro
お気に入りにしたユーザー ProblemId : 8616 / 自分の提出
問題文最終更新日: 2022-11-08 00:27:13
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 369 (順位表) の他の問題:

Problem Statement

You are given positive integers $N$ and $M$ as input.

　

Torus-Loving Bot, as you know, is a bot that loves donuts.

Torus-Loving-Bot-Loving Bot, as you know, is a bot that loves Torus-Loving Bot. Of course, the $2$ bots are different entities.

One day, you bought Torus-Loving Bot and Torus-Loving-Bot-Loving Bot a total of $N$ kinds of donuts, $1$ of each kind.

You want to distribute these $N$ kinds of donuts to the $2$ bots, but Torus-Loving Bot will cry unless it receives at least $M$ donuts.

　

Find the total number of ways to distribute the $N$ kinds of donuts to the $2$ bots so that Torus-Loving Bot does not cry, modulo $998244353$.

Here, when counting the total number of ways to distribute, donuts of different kinds are distinguished.

Input

Input is given from standard input in the following format: 
$N$
$M$

Constraints

The input satisfies the following constraints:

  • $N$ is a positive integer at most $10^{18}$
  • $M$ is a positive integer at most $10^5$

Output

Output the total number of ways to distribute the $N$ kinds of donuts to the $2$ bots so that Torus-Loving Bot does not cry, modulo $998244353$.

Print a newline at the end.

Sample

Sample 1
Input
1
1
Output
1

You bought $1$ kind of donut, $1$ of each kind, so the only way to distribute so that Torus-Loving Bot does not cry by giving Torus-Loving Bot at least $1$ kind is

  • giving the $1$ donut you bought to Torus-Loving Bot and giving nothing to Torus-Loving-Bot-Loving Bot

which is just $1$ way. The remainder when $1$ is divided by $998244353$ is $1$.

Sample 2
Input
1
2
Output
0

You bought only $1$ kind of donut, $1$ of each kind, so there is no way to distribute by giving Torus-Loving Bot at least $2$ donuts so that Torus-Loving Bot does not cry. The remainder when $0$ is divided by $998244353$ is $0$.

Sample 3
Input
2
1
Output
3

You bought $2$ kinds of donuts, $1$ of each kind. Calling them Donut A and Donut B, the ways to distribute so that Torus-Loving Bot does not cry by giving Torus-Loving Bot at least $1$ donut are

  • giving Donut A to Torus-Loving Bot and Donut B to Torus-Loving-Bot-Loving Bot
  • giving Donut B to Torus-Loving Bot and Donut A to Torus-Loving-Bot-Loving Bot
  • giving Donut A and Donut B to Torus-Loving Bot and no donuts to Torus-Loving-Bot-Loving Bot

which are $3$ ways. The remainder when $3$ is divided by $998244353$ is $3$.

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