Score : $600$ points
There are $K$ robots on a number line. The $i$-th robot $(1 \leq i \leq K)$ is initially at the coordinate $x_i$.
The following procedure is going to take place exactly $N$ times.
Here, all probabilistic decisions are independent.
Find the probability that no two robots meet, that is, there are never two or more robots at the same coordinate at the same time throughout the procedures, modulo $998244353$ (see Notes).
It can be proved that the probability in question is always a rational number. Additionally, under the Constraints in this problem, when that value is represented as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, it can be proved that there uniquely exists an integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find this $R$.
Input is given from Standard Input in the following format:
$K$ $N$ $x_1$ $x_2$ $\ldots$ $x_K$
Print the answer.
2 2 1 2
374341633
The probability in question is $\frac{5}{8}$.
We have $374341633 \times 8 \equiv 5\pmod{998244353}$, so you should print $374341633$.
2 2 10 100
1
The probability in question may be $1$.
10 832 73 160 221 340 447 574 720 742 782 970
553220346
配点 : $600$ 点
数直線上に $K$ 個のロボットが置かれています。$i \, (1 \leq i \leq K)$ 番目のロボットははじめ、座標 $x_i$ に存在します。
これから以下の操作をちょうど $N$ 回行います。
ただし、すべての確率的な決定は独立であるとします。
一連の操作の中で、複数のロボットが出会う、すなわち $2$ 個以上のロボットが同時に同じ座標に存在する、という事象が一度も起こらない確率を$\mod 998244353$ で求めてください（注記参照）。
求める確率は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P$, $Q$ を用いて $\frac{P}{Q}$ と表したとき、$R \times Q \equiv P\pmod{998244353}$ かつ $0 \leq R \lt 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。
入力は以下の形式で標準入力から与えられる。
$K$ $N$ $x_1$ $x_2$ $\ldots$ $x_K$
答えを出力せよ。
2 2 1 2
374341633
求める確率は $\frac{5}{8}$ です。
$374341633 \times 8 \equiv 5\pmod{998244353}$ ですので、$374341633$ を出力します。
2 2 10 100
1
求める確率が $1$ であることもあります。
10 832 73 160 221 340 447 574 720 742 782 970
553220346