[ARC109E] 1D Reversi Builder

有一个长为 $n$ 的表格，将每个格子等概率随机染成黑色或白色。 初始标记第 $x$ 个格子，有两个人进行博弈，每次可以选择标记一个未被标记的格子，满足相邻的某个格子已被标记。设选择的格子颜色为 $c$，然后找到与当前格子最近的颜色为 $c$ 的格子，并将这两个格子之间的一段区间均染成 $c$。 先手想要最大化最终黑色的格子数，后手反之，问最终黑色格子数的期望。

[problemUrl]: https://atcoder.jp/contests/arc109/tasks/arc109_e 黒石さんと白石さんは、一列に並んだ $ n $ 個のマスからなる盤面を使って遊んでいます。 マスにはそれぞれ $ 1 $ から $ n $ の整数が順番に振られていて、マス $ s $ に印がつけられています。 まず、黒石さんは、各マスについて独立に、黒か白を等確率で選んで塗ります。その後、マス $ s $ にマスの色と同じ色の石を置きます。 黒石さんと白石さんは、この盤面と無限個の黒い石と白い石を使ったゲームをします。このゲームでは、黒石さんから始めて、黒石さんと白石さんが交互に次の手順で石を置いていきます。 1. 石が置かれているマスと隣接している空きマスをひとつ選ぶ。マス $ i $ を選んだとする。 2. マス $ i $ に、マスと同じ色の石をおく。 3. 置いた石と同じ色の石がマス $ i $ 以外に置かれているとき、そのうちマス $ i $ に最も近い石と、マス $ i $ の間にあるすべての石の色をマス $ i $ の色に変更する 空きマスが存在しなくなったときにゲームが終了します。 黒石さんはゲーム終了時の黒い石の個数を最大化するために最適な行動をし、白石さんはゲーム終了時の白い石の個数を最大化するために最適な行動をします。 $ s=1,\dots,n $ それぞれの場合について、ゲーム終了時の黒い石の個数の期待値を $ \text{mod\ }998244353 $ で求めてください。

入力は以下の形式で標準入力から与えられる。 > $ n $

$ n $ 個の値を出力せよ。 $ i $ 個目には、$ s=i $ としたときのゲーム終了時の黒い石の個数の期待値を $ \text{mod\ }998244353 $ で出力せよ。

3

499122178
499122178
499122178

10

5
5
992395270
953401350
735035398
735035398
953401350
992395270
5
5

19

499122186
499122186
499110762
499034602
498608106
496414698
485691370
434999274
201035754
138645483
201035754
434999274
485691370
496414698
498608106
499034602
499110762
499122186
499122186

### 注意 求める期待値が既約分数 $ p/q $ で表されるとき、$ rq\equiv\ p\ ~(\text{mod\ }\ 998244353) $ かつ $ 0\ \leq\ r\ \lt\ 998244353 $ を満たす整数 $ r $ がこの問題の制約のもとで一意に定まります。この $ r $ が求める値です。 ### 制約 - $ 1\ \leq\ n\ \leq\ 2\times\ 10^5 $ ### Sample Explanation 1 黒マスを `b` で、白マスを `w` で表すことにします。 盤面として、`www`, `wwb`, `wbw`, `wbb`, `bww`, `bwb`, `bbw`, `bbb` の $ 8 $ 通りがあり、これらから等確率に $ 1 $ つが選ばれます。 $ s $ によらず、それぞれの盤面について、ゲーム終了時の黒い石の個数は $ 0,1,0,2,1,3,2,3 $ となります。 よって、期待値は $ (0+1+0+2+1+3+2+3)/8\ =\ 3/2 $ となるため、答えは $ 2r\ \equiv\ 3\ ~(\text{mod\ }\ 998244353) $ かつ $ 0\ \leq\ r\ \lt\ 998244353 $ を満たす $ r\ =\ 499122178 $ となります。