题解 | #游戏#

考虑用dp解决问题

我们设$l_{i,j}l\_\{i,j\}$表示到第i个人最后一个人赢的选择为第j个选择的概率

设$r_{i,j}r\_\{i,j\}$表示上一个人赢的选择为第j个选择并且它会一直赢到最后的概率

那么就有转移方程（get(i,j)表示在第i个人中选择j的概率）

$l_{i,j}=l_{i-1,j}\times (get(i,j)+get(i,(j+1)\mathrm{\%}3))+l_{i-1,(j+1)\mathrm{\%}3}+get(i,j)l\_\{i,j\}=l\_\{i-1,j\}\times (get(i,j)+get(i,(j+1)\backslash \%3))+l\_\{i-1,(j+1)\backslash \%3\}+get(i,j)$

这个方程的意思是当上一个人的选择为 j 的时候，目前这个人选择j或者j+1都会输并且得到现在的结果 j

而当上一个选择为 j+1 的时候，目前这个人选择j会赢并且现在的结果是 j

$r_{i,j}=r_{i+1,j}\ast (get(i,j)+get(i,(j+1)\mathrm{\%}3))r\_\{i,j\}=r\_\{i+1,j\}*(get(i,j)+get(i,(j+1)\backslash \%3))$

这个方程的意思是因为如果一个人赢那么它要一直赢下去，它选了石头之后就一直要出石头（题目说一个人整局只会出一种手势）

那就从后往前枚举赢的情况就行了

最后把每个人手势情况输出一遍就行了，上一个人最后一个手势赢的情况×目前这个人手势的情况×这个手势之后一直赢的情况就是答案

注意取模和边界处理

#define int long long
using namespace std;
const int N=1e5+10;
const int mod=998244353;
string s[N];
int l[N][3],r[N][3];
int ksm(int a,int b){
      int cnt=1;
      while(b){
        if(b&1)cnt=cnt*a%mod;
        a=a*a%mod;
        b>>=1;
      }
      return cnt;
}
int get(int a,int b){
    int sum=0,cnt=(s[a][b]=='1');
    for(int i=0;i<3;i++)sum+=(s[a][i]=='1');
    return cnt*ksm(sum,mod-2)%mod;
}
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=0;i<3;i++)l[1][i]=get(1,i),l[0][i]=1;
    for(int i=2;i<=n;i++)
        for(int j=0;j<3;j++)
            l[i][j]=(l[i-1][j]*(get(i,j)+get(i,(j+1)%3))%mod+l[i-1][(j+1)%3]*get(i,j)%mod)%mod;
    for(int i=0;i<3;i++)r[n][i]=(get(n,i)+get(n,(i+1)%3))%mod,r[n+1][i]=1;
    for(int i=n-1;i>=1;i--)
        for(int j=0;j<3;j++)
            r[i][j]=r[i+1][j]*(get(i,j)+get(i,(j+1)%3))%mod;
    for(int i=1;i<=n;i++){
        int ans=0;
        for(int j=0;j<3;j++)ans=(ans+l[i-1][(j+1)%3]*get(i,j)%mod*r[i+1][j]%mod)%mod;
        cout<<ans<<' ';
    }
    return 0;
}