/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
Score : 600 points
Problem Statement
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.
- Each robot chooses to move or not with probability \frac{1}{2} each. The robots that move will simultaneously go the distance of 1 in the positive direction, and the other robots will remain still.
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).
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.
Constraints
- 2 \leq K \leq 10
- 1 \leq N \leq 1000
- 0 \leq x_1 \lt x_2 \lt \cdots \lt x_K \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
K N x_1 x_2 \ldots x_K
Output
Print the answer.
Sample Input 1
2 2 1 2
Sample Output 1
374341633
The probability in question is \frac{5}{8}.
We have 374341633 \times 8 \equiv 5\pmod{998244353}, so you should print 374341633.
Sample Input 2
2 2 10 100
Sample Output 2
1
The probability in question may be 1.
Sample Input 3
10 832 73 160 221 340 447 574 720 742 782 970
Sample Output 3
553220346
配点 : 600 点
問題文
数直線上に K 個のロボットが置かれています。i \, (1 \leq i \leq K) 番目のロボットははじめ、座標 x_i に存在します。
これから以下の操作をちょうど N 回行います。
- K 個のロボットそれぞれについて、「進む」か「止まる」かを確率 \frac{1}{2} で決める。「進む」と決めたロボットたちは同時に正の方向に 1 進み、「止まる」と決めたロボットたちはその場から動かない。
ただし、すべての確率的な決定は独立であるとします。
一連の操作の中で、複数のロボットが出会う、すなわち 2 個以上のロボットが同時に同じ座標に存在する、という事象が一度も起こらない確率を\mod 998244353 で求めてください（注記参照）。
注記
求める確率は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。
制約
- 2 \leq K \leq 10
- 1 \leq N \leq 1000
- 0 \leq x_1 \lt x_2 \lt \cdots \lt x_K \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
K N x_1 x_2 \ldots x_K
出力
答えを出力せよ。
入力例 1
2 2 1 2
出力例 1
374341633
求める確率は \frac{5}{8} です。
374341633 \times 8 \equiv 5\pmod{998244353} ですので、374341633 を出力します。
入力例 2
2 2 10 100
出力例 2
1
求める確率が 1 であることもあります。
入力例 3
10 832 73 160 221 340 447 574 720 742 782 970
出力例 3
553220346