E - 1D Reversi Builder

Contest Duration: 2020-11-28 21:00:00+0900 - 2020-11-28 23:00:00+0900 (local time) (120 minutes) Back to Home

E - 1D Reversi Builder Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

黒石さんと白石さんは、一列に並んだ n 個のマスからなる盤面を使って遊んでいます。マスにはそれぞれ 1 から n の整数が順番に振られていて、マス s に印がつけられています。

まず、黒石さんは、各マスについて独立に、黒か白を等確率で選んで塗ります。その後、マス s にマスの色と同じ色の石を置きます。

黒石さんと白石さんは、この盤面と無限個の黒い石と白い石を使ったゲームをします。このゲームでは、黒石さんから始めて、黒石さんと白石さんが交互に次の手順で石を置いていきます。

石が置かれているマスと隣接している空きマスをひとつ選ぶ。マス i を選んだとする。
マス i に、マスと同じ色の石をおく。
置いた石と同じ色の石がマス i 以外に置かれているとき、そのうちマス i に最も近い石と、マス i の間にあるすべての石の色をマス i の色に変更する

空きマスが存在しなくなったときにゲームが終了します。

黒石さんはゲーム終了時の黒い石の個数を最大化するために最適な行動をし、白石さんはゲーム終了時の白い石の個数を最大化するために最適な行動をします。

s=1,\dots,n それぞれの場合について、ゲーム終了時の黒い石の個数の期待値を \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

入力

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

出力

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

入力例 1

出力例 1

499122178
499122178
499122178

黒マスを 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 となります。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 700 points

Problem Statement

Kuro and Shiro are playing with a board composed of n squares lining up in a row. The squares are numbered 1 to n from left to right, and Square s has a mark on it.

First, for each square, Kuro paints it black or white with equal probability, independently from other squares. Then, he puts on Square s a stone of the same color as the square.

Kuro and Shiro will play a game using this board and infinitely many black stones and white stones. In this game, Kuro and Shiro alternately put a stone as follows, with Kuro going first:

Choose an empty square adjacent to a square with a stone on it. Let us say Square i is chosen.
Put on Square i a stone of the same color as the square.
If there are squares other than Square i that contain a stone of the same color as the stone just placed, among such squares, let Square j be the one nearest to Square i. Change the color of every stone between Square i and Square j to the color of Square i.

The game ends when the board has no empty square.

Kuro plays optimally to maximize the number of black stones at the end of the game, while Shiro plays optimally to maximize the number of white stones at the end of the game.

For each of the cases s=1,\dots,n, find the expected value, modulo 998244353, of the number of black stones at the end of the game.

Notes

When the expected value in question is represented as an irreducible fraction p/q, there uniquely exists an integer r such that rq=p ~(\text{mod } 998244353) and 0 \leq r \lt 998244353, which we ask you to find.

Constraints

1 \leq n \leq 2\times 10^5

Input

Input is given from Standard Input in the following format:

Output

Print n values. The i-th value should be the expected value, modulo 998244353, of the number of black stones at the end of the game for the case s=i.

Sample Input 1

Sample Output 1

499122178
499122178
499122178

Let us use b to represent a black square and w to represent a white square. There are eight possible boards: www, wwb, wbw, wbb, bww, bwb, bbw, and bbb, which are chosen with equal probability.

For each of these boards, there will be 0, 1, 0, 2, 1, 3, 2, and 3 black stones at the end of the game, respectively, regardless of the value of s. Thus, the expected number of stones is (0+1+0+2+1+3+2+3)/8 = 3/2, and the answer is r = 499122178, which satisfies 2r = 3 ~(\text{mod } 998244353) and 0 \leq r \lt 998244353.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3