102817: [AtCoder]ABC281 Ex - Alchemy
Description
Score : $600$ points
Problem Statement
Takahashi has $A$ kinds of level-$1$ gems, and $10^{10^{100}}$ gems of each of those kinds.
For an integer $n$ greater than or equal to $2$, he can put $n$ gems that satisfy all of the following conditions into a cauldron to generate a level-$n$ gem in return.
- No two gems are of the same kind.
- Every gem's level is less than $n$.
- For every integer $x$ greater than or equal to $2$, there is at most one level-$x$ gem.
Find the number of kinds of level-$N$ gems that Takahashi can obtain, modulo $998244353$.
Here, two level-$2$ or higher gems are considered to be of the same kind if and only if they are generated from the same set of gems.
- Two sets of gems are distinguished if and only if there is a gem in one of those sets such that the other set does not contain a gem of the same kind.
Any level-$1$ gem and any level-$2$ or higher gem are of different kinds.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A \leq 10^9$
- $N$ and $A$ are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A$
Output
Print the answer.
Sample Input 1
3 3
Sample Output 1
10
Here are ten ways to obtain a level-$3$ gem.
- Put three kinds of level-$1$ gems into the cauldron.
- Takahashi has three kinds of level-$1$ gems, so there is one way to choose three kinds of level-$1$ gems. Thus, he can obtain one kind of level-$3$ gem in this way.
- Put one kind of level-$2$ gem and two kinds of level-$1$ gems into the cauldron.
- A level-$2$ gem can be obtained by putting two kinds of level-$1$ gems into the cauldron.
- Takahashi has three kinds of level-$1$ gems, so there are three ways to choose two kinds of level-$1$ gems. Thus, three kinds of level-$2$ gems are available here.
- There are three kinds of level-$2$ gems, and three ways to choose two kinds of level-$1$ gems, so he can obtain $3 \times 3 = 9$ kinds of level-$3$ gems in this way.
- A level-$2$ gem can be obtained by putting two kinds of level-$1$ gems into the cauldron.
Sample Input 2
1 100
Sample Output 2
100
Sample Input 3
200000 1000000000
Sample Output 3
797585162
Input
题意翻译
高桥君有 $A$ 种等级 $1$ 的宝石，宝石数量充分多。 他可以利用 $n$ 个满足以下条件的宝石来合成一个等级 $n$ 的宝石（$n\geq 2$）。 - 不存在相同种类的宝石。 - 每个宝石的等级严格小于 $n$。 - 对于 $\geq 2$ 的等级，每等级最多有 $1$ 个宝石。 求高桥君能获得等级 $N$ 宝石的种类数，对 $998244353$ 取模。 对于等级 $\geq 2$ 的宝石，种类相同当且仅当合成它们的宝石的种类完全相同。任意等级不同的宝石，种类一定不同。Output
得分：600分
问题描述
高桥有$A$种等级为1的宝石，每种宝石有$10^{10^{100}}$个。
对于大于等于2的整数$n$，他可以将满足以下所有条件的$n$个宝石放入炼金锅中，以生成等级为$n$的宝石作为回报。
- 没有两个宝石是同一种类的。
- 每个宝石的等级都小于$n$。
- 对于大于等于2的整数$x$，最多有一个等级为$x$的宝石。
求高桥可以得到的等级为$N$的宝石种类数，对$998244353$取模。
这里，两个等级为2或更高的宝石被认为只有当它们由同一组宝石生成时才是同一种类。
- 只有当其中一个集合中存在一个宝石，另一个集合中没有同种类的宝石时，这两组宝石才能区分。
任何等级为1的宝石和任何等级为2或更高的宝石都是不同的种类。
约束条件
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A \leq 10^9$
- $N$和$A$都是整数。
输入
输入从标准输入中以以下格式给出：
$N$ $A$
输出
打印答案。
样例输入1
3 3
样例输出1
10
这里有十种方法可以得到一个等级为3的宝石。
- 将三种等级为1的宝石放入炼金锅中。
- 高桥有三种等级为1的宝石，所以他有1种方法可以选择三种等级为1的宝石。因此，他可以通过这种方式得到一种等级为3的宝石。
- 将一种等级为2的宝石和两种等级为1的宝石放入炼金锅中。
- 一个等级为2的宝石可以通过将两种等级为1的宝石放入炼金锅中得到。
- 高桥有三种等级为1的宝石，所以他有3种方法可以选择两种等级为1的宝石。因此，这里有三种等级为2的宝石可用。
- 这里有三种等级为2的宝石，以及三种选择两种等级为1的宝石的方法，所以他可以通过这种方式得到$3 \times 3 = 9$种等级为3的宝石。
- 一个等级为2的宝石可以通过将两种等级为1的宝石放入炼金锅中得到。
样例输入2
1 100
样例输出2
100
样例输入3
200000 1000000000
样例输出3
797585162