103604: [Atcoder]ABC360 E - Random Swaps of Balls
Description
Score : $450$ points
Problem Statement
There are $N - 1$ white balls and one black ball. These $N$ balls are arranged in a row, with the black ball initially at the leftmost position.
Takahashi will perform the following operation exactly $K$ times.
- Choose an integer uniformly at random between $1$ and $N$, inclusive, twice. Let $a$ and $b$ the chosen integers. If $a \neq b$, swap the $a$-th and $b$-th balls from the left.
After $K$ operations, let the black ball be at the $x$-th position from the left. Find the expected value of $x$, modulo $998244353$.
What is expected value modulo $998244353$?
It can be proved that the sought expected value will always be rational. Additionally, under the constraints of this problem, it can be proved that if this value is expressed as an irreducible fraction $\frac{P}{Q}$, then $Q \not \equiv 0 \pmod{998244353}$. Therefore, there exists a unique integer $R$ such that $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$. Report this $R$.Constraints
- $1 \leq N \leq 998244352$
- $1 \leq K \leq 10^5$
Input
The input is given from Standard Input in the following format:
$N$ $K$
Output
Print the answer in one line.
Sample Input 1
2 1
Sample Output 1
499122178
After one operation, the probabilities that the black ball is at the 1st position and the 2nd position from the left are both $\displaystyle \frac{1}{2}$. Thus, the expected value is $\displaystyle \frac{3}{2}$.
Sample Input 2
3 2
Sample Output 2
554580198
Sample Input 3
4 4
Sample Output 3
592707587
Output
问题说明
有$N - 1$个白球和一个黑球。这$N$个球排成一行，黑球最初位于最左边的位置。
高桥将执行以下操作正好$K$次。
- 在$1$和$N$之间（包括$1$和$N$）均匀随机地选择两个整数。设$a$和$b$为选定的整数。如果$a \neq b$，则交换从左边数第$a$个和第$b$个球。
经过$K$次操作后，设黑球位于从左边数第$x$个位置。求$x$的期望值，模$998244353$。
什么是模$998244353$的期望值？
可以证明，所求的期望值总是有理数。此外，在这个问题的约束下，可以证明，如果这个值表示为不可约分数$\frac{P}{Q}$，那么$Q \not \equiv 0 \pmod{998244353}$。因此，存在一个唯一的整数$R$使得$R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$。报告这个$R$。约束条件
- $1 \leq N \leq 998244352$
- $1 \leq K \leq 10^5$
输入
输入从标准输入以以下格式给出：
$N$ $K$
输出
在一行中打印答案。
示例输入1
2 1
示例输出1
499122178
经过一次操作后，黑球位于从左边数第1个位置和第2个位置的概率都是$\displaystyle \frac{1}{2}$。因此，期望值是$\displaystyle \frac{3}{2}$。
示例输入2
3 2
示例输出2
554580198
示例输入3
4 4
示例输出3
592707587