/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 600 点
問題文
高橋君はこれから N 日間についての勤務予定を、各日を勤務日か休日のどちらかに設定することで作成しようとしています。
勤務に関する条件を表す長さ N の文字列 S が与えられます。
S の i 文字目が x のとき i 日目は必ず勤務日にしなければなりません。. のとき i 日目は勤務日と休日のどちらにすることもできます。
条件を満たす勤務予定は S に含まれる . の個数を q としたとき全部で 2^q 通り考えられます。
k=1,2,\dots,N について次の問題を解いてください。
条件を満たす勤務予定 2^q 通りのうち、最長の連続する休日がちょうど k 日であるような決め方の総数を 998244353 で割ったあまりを求めてください。
制約
- N は 1 以上 2 \times 10^5 以下の整数
- S は
.,xからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
N 行出力せよ。i 行目には k=i のときの答えを出力せよ。
入力例 1
5 .x...
出力例 1
9 4 2 0 0
休日を o で表すとき、条件を満たす勤務予定はそれぞれ以下のようになります。
- k=1：
oxxxx,oxoxx,oxoxo,oxxox,oxxxo,xxoxx,xxoxo,xxxox,xxxxo - k=2：
oxoox,oxxoo,xxoox,xxxoo - k=3：
oxooo,xxooo
入力例 2
7 .......
出力例 2
33 47 27 12 5 2 1
入力例 3
20 .....x...x..........
出力例 3
9359 75312 94664 46840 23680 7168 3072 1280 512 256 0 0 0 0 0 0 0 0 0 0
Score : 600 points
Problem Statement
Takahashi is creating a work schedule for N days by designating each day as a workday or a holiday.
You are given a string S of length N representing the constraints on work days.
If the i-th character of S is x, day i must be a workday. If it is ., day i can be either a workday or a holiday.
There are 2^q valid work schedules satisfying the constraints, where q is the number of . characters in S.
For each k=1,2,\dots,N, solve the following problem:
Among the 2^q valid work schedules satisfying the constraints, find the number, modulo 998244353, of schedules in which the longest consecutive block of holidays is exactly k days.
Constraints
- N is an integer between 1 and 2 \times 10^5, inclusive.
- S is a string of length N consisting of
.,x.
Input
The input is given from Standard Input in the following format:
N S
Output
Output N lines. The i-th line should contain the answer for k=i.
Sample Input 1
5 .x...
Sample Output 1
9 4 2 0 0
Denoting holidays as o, the valid work schedules are as follows:
- k=1:
oxxxx,oxoxx,oxoxo,oxxox,oxxxo,xxoxx,xxoxo,xxxox,xxxxo - k=2:
oxoox,oxxoo,xxoox,xxxoo - k=3:
oxooo,xxooo
Sample Input 2
7 .......
Sample Output 2
33 47 27 12 5 2 1
Sample Input 3
20 .....x...x..........
Sample Output 3
9359 75312 94664 46840 23680 7168 3072 1280 512 256 0 0 0 0 0 0 0 0 0 0