B-游戏_牛客挑战赛59

游戏

比赛主页

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有 $n$ 个人玩石头剪刀布，分别编号为 $1,2,\cdots,n$ ，每个人在决定好要出什么手势后，整局游戏都只会出这种手势。

游戏进行 $n-1$ 轮，第 $1$ 轮由 $1,2$ 两人进行比赛，第 $i\ (2 \le i \le n-1)$ 轮由 $i-1$ 轮的获胜者与第 $i+1$ 个人进行比赛，胜利者根据如下规则判断：

如果两人中一人出石头，一人出剪刀，则手势为石头的人获胜。
如果两人中一人出石头，一人出布，则手势为布的人获胜。
如果两人中一人出布，一人出剪刀，则手势为剪刀的人获胜。
否则如果两人手势一样，编号小的获胜。

你知道每个人可能决定要出的手势集合，并且每个人都会等概率地从自己的集合中选择一个手势，现在请你求出所有可能中每个人的获胜概率。

答案对 $998244353$ 取模。

输入描述:

第一行一个整数 $n\ (2 \le n \le 10^5)$ 表示人数。

接下来 $n$ 行，第 $i$ 行输入一个长度为 $3$ 的仅包含 $01$ 的字符串 $s_i$

若 $s_{i,1}=1$ 则第 $i$ 个人的手势集合包含石头。

若 $s_{i,2}=1$ 则第 $i$ 个人的手势集合包含剪刀。

若 $s_{i,3}=1$ 则第 $i$ 个人的手势集合包含布。

数据保证 $s_i$ 中至少存在一个 $1$ 。

输出描述:

一行输出 $n$ 个数分别表示第 $i$ 个人获胜的概率对 $998244353$ 取模的结果。

一个有理数 $\dfrac{P}{Q}$ 对一个质数模数 $\text{mod}$ 取模的结果为 $P \times Q^{\text{mod}-2}$

示例1

输入

复制

输出

复制

776412275 0 443664157 776412275

说明

四个人获胜的概率分别为  。