← 返回题目列表

AtCoder · abc456_g

G. 计算假期

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

高桥正在制定工作时间表 N 天,将每一天指定为工作日或假期。

给你一个字符串 S 长度 N 代表工作日的限制。 如果 i- 第一个字符 S is x,日 i 必须是工作日。如果是的话 .,日 i 可以是工作日或节假日。

有 2^q 满足约束条件的有效工作计划,其中 q 是数量 . 中的字符 S。 对于每个 k=1,2,\dots,N,解决以下问题:

其中 2^q 满足约束条件的有效工作计划,找到数量,取模 998244353,其中最长的连续假期正好是 k 天。

约束

  • N 是介于 1 和 2 \times 10^5,包括在内。
  • S 是一个长度为的字符串 N 组成 ., x.

输入

输入由标准输入按以下格式给出:

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