UOJ Logo Universal Online Judge

UOJ

附件下载 统计

English Problem Statement

在智能电网的建设过程中,伏特需要做一些电学实验。作为电磁学高手,伏特设计了一个机器来研究电子的运动。

这个机器由 n 个排成一行的舱室组成。每个舱室内部有磁场,可以看作有一个为 +- 的状态。

电子的运动规律如下:

  • 假设在某个舱室 i 有一个电子。
  • 如果电子所在舱室的状态是 -,就会向左移动到 i1 的舱室,否则会向右移动到 i+1 的舱室。
  • 在移动之后,电子原本所在的 i 号舱室会翻转状态(从 - 变成 +,或从 + 变成 -)。
  • 如果电子掉到外面(0n+1 的位置),运动过程就结束了,否则会继续运动。

伏特提出了以下问题:

  • 现在每个舱室的状态是 +/-/?
  • 在实验开始前,伏特会以 12 的概率把每个 ? 的舱室设定为 +/- 的状态。
  • 然后伏特以 px 的概率在 x 处放一个电子,让电子不断运动,直到掉到外面。
  • 设最后电子掉到外面后,有恰好 i 个舱室状态为 + 的概率是 ansi

你需要求出所有 ansi,答案对 998244353 取模。

输入格式

第一行一个整数 n

第二行 n 个整数,表示 p1pn

第三行一个长度为 n 的字符串 s,每个字符为 +/-/? 的其中之一,表示每个舱室的状态。

输出格式

输出 n+1 个整数,表示 ans0ansn

样例一

input

3
499122177 748683265 748683265
+?-

output

748683265 873463809 748683265 623902721

样例解释 1

初始的 pi 分别为 12,14,14

ans0ansn 分别为 28,18,28,38

以下是一种可能的运动过程:

  • 初始电子处于 1 位置,状态为 +--
  • 电子运动到 2 位置,状态为 ---
  • 电子运动到 1 位置,状态为 -+-
  • 电子运动到 0 位置,状态为 ++-。此时运动结束。

样例二

input

5
499122177 748683265 873463809 935854081 935854081
?+-??

output

889061377 935854081 904658945 772079617 701890561 787677185

样例解释 2

初始的 pi 分别为 12,14,18,116,116

样例三 ~ 十

见下发文件。

数据范围

对于所有数据,保证 1n5×1050pi<998244353(pi)mod998244353=1

子任务编号 n 子任务分值
1 15 6
2 40 12
3 500 16
4 1500 14
5 6000 16
6 3×104 12
7 2×105 12
8 5×105 12

时间限制:2s

空间限制:2GB