在智能电网的建设过程中,伏特需要做一些电学实验。作为电磁学高手,伏特设计了一个机器来研究电子的运动。
这个机器由 +
或 -
的状态。
电子的运动规律如下:
- 假设在某个舱室
有一个电子。 - 如果电子所在舱室的状态是
-
,就会向左移动到 的舱室,否则会向右移动到 的舱室。 - 在移动之后,电子原本所在的
号舱室会翻转状态(从-
变成+
,或从+
变成-
)。 - 如果电子掉到外面(
或 的位置),运动过程就结束了,否则会继续运动。
伏特提出了以下问题:
- 现在每个舱室的状态是
+/-/?
。 - 在实验开始前,伏特会以
的概率把每个?
的舱室设定为+/-
的状态。 - 然后伏特以
的概率在 处放一个电子,让电子不断运动,直到掉到外面。 - 设最后电子掉到外面后,有恰好
个舱室状态为+
的概率是 。
你需要求出所有
输入格式
第一行一个整数
第二行
第三行一个长度为 +/-/?
的其中之一,表示每个舱室的状态。
输出格式
输出
样例一
input
3 499122177 748683265 748683265 +?-
output
748683265 873463809 748683265 623902721
样例解释 1
初始的
以下是一种可能的运动过程:
- 初始电子处于
位置,状态为+--
。 - 电子运动到
位置,状态为---
。 - 电子运动到
位置,状态为-+-
。 - 电子运动到
位置,状态为++-
。此时运动结束。
样例二
input
5 499122177 748683265 873463809 935854081 935854081 ?+-??
output
889061377 935854081 904658945 772079617 701890561 787677185
样例解释 2
初始的
样例三 ~ 十
见下发文件。
数据范围
对于所有数据,保证
子任务编号 | 子任务分值 | |
---|---|---|
时间限制:
空间限制: