AT_arc133_f [ARC133F] Random Transition
Description
[problemUrl]: https://atcoder.jp/contests/arc133/tasks/arc133_f
整数 $ N $ が与えられます.
すぬけくんはこれから,以下の操作を行います.
- 変数 $ x $ を用意し,ランダムに選んだ $ 0 $ 以上 $ N $ 以下の整数で初期化する.各 $ 0\ \leq\ i\ \leq\ N $ に対し,$ x=i $ と初期化する確率は $ A_i/10^9 $ である.
- 次の操作を $ K $ 回繰り返す.
- 確率 $ x/N $ で $ x $ の値を $ 1 $ 減らし,確率 $ 1-x/N $ で $ x $ の値を $ 1 $ 増やす. (ここで,操作後も $ x $ の値が必ず $ 0 $ 以上 $ N $ 以下であることに注意)
各 $ i=0,1,\cdots,N $ について,すべての操作が終了したあとに $ x=i $ である確率を $ \pmod{998244353} $ で求めてください.
確率 $ \pmod{998244353} $ の定義 求める確率は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $ \frac{P}{Q} $ で表した時、$ Q\ \neq\ 0\ \pmod{998244353} $ となることも証明できます。 よって、$ R\ \times\ Q\ \equiv\ P\ \pmod{998244353},\ 0\ \leq\ R\ <\ 998244353 $ を満たす整数 $ R $ が一意に定まります。 この $ R $ を答えてください。
Input Format
N/A
Output Format
N/A
Explanation/Hint
### 制約
- $ 1\ \leq\ N\ \leq\ 100000 $
- $ 0\ \leq\ A_i $
- $ \sum_{0\ \leq\ i\ \leq\ N}A_i\ =\ 10^9 $
- $ 1\ \leq\ K\ \leq\ 10^9 $
- 入力される値はすべて整数である
### Sample Explanation 1
最初は必ず $ x=1 $ と初期化します. その後の操作では.確率 $ 1/2 $ で $ x $ の値を $ 1 $ 減らし,確率 $ 1/2 $ で $ x $ の値を $ 1 $ 増やします. 最終的に $ x=0,1,2 $ となる確率は,それぞれ $ 1/2,0,1/2 $ です.