AT_arc109_e [ARC109E] 1D Reversi Builder

[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 $ で出力せよ。

### 注意 求める期待値が既約分数 $ 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 $ となります。