分数: 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