题解 | #游戏#
游戏
https://ac.nowcoder.com/acm/contest/11199/B
本来一开始就写完了...
可惜读错题了,我读的题更复杂一点点...
所以越写到后面脑子越晕...
直接导致后面调傻了,在原代码上.
我读的题里面他是每一轮都可以出它集合里面的东西.而不是固定一种.
两者处理方法是一样的,但是前者更为复杂?
好了...
考虑第个人怎么才能赢,那么就是第个人赢了,前轮的胜利者,然后赢了后面所有人对吧?
然后赢了后面所有人怎么考虑,那么可以用个后缀和,统计后面每种状态的个数,显然只有7种状态,然后把他们按照乘法原理就可以算出来了.
假设我后面状态为111(7)的有4种,我当前为100(4),那么概率不就是的4次方嘛?
表示我现在是哪种,我的对手是哪种,我赢的概率.保证对手在后面.
考虑前面赢的是哪种,可以定义.可以发现赢哪个和人无关只是和它的手势有关.
那么定义到了第个人,赢的是的概率.
考虑状态更新.
就有两种,一种是前面赢了后面的还是这个状态,一种是当前是的子集,我赢了前面的概率,当然答案是边算边更新,所以我们新更新后者计算答案,然后再去算前者.
代码变量名都有注释.思路还是很清晰的~
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int M=8;
const int mod=998244353;
ll nums[N][M];
ll pre[M][M];//我现在是哪种,我的对手是哪种,我赢的概率.保证对手在前面.
ll suf[M][M];//我现在是哪种,我的对手是哪种,我赢的概率.保证对手在后面.
ll f[N][M];//到了第i个人,赢的是j的概率.
ll g[N][M];
ll ans[N];//第i个人赢到最后的概率.
string s[N];
int a[N];
int bit[M];
ll qp(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
ll prebeat(int a,int b)//我是a,敌人是b,敌人在前面我击败它的概率.
{
ll res=0;
ll A=a;
if(A&1)
if(b&(1<<1)) res=(res+qp(bit[a],mod-2)*qp(bit[b],mod-2))%mod;
A>>=1;
if(A&1)
if(b&(1<<2)) res=(res+qp(bit[a],mod-2)*qp(bit[b],mod-2))%mod;
A>>=1;
if(A&1)
if(b&(1<<0)) res=(res+qp(bit[a],mod-2)*qp(bit[b],mod-2))%mod;
return res;
}
ll sufbeat(int a,int b)//我是a,敌人是b,敌人在后面我击败它的概率.
{
ll res=0;
ll A=a;
if(A&1)
{
if(b&(1<<1)) res=(res+qp(bit[a],mod-2)*qp(bit[b],mod-2))%mod;
if(b&(1<<0)) res=(res+qp(bit[a],mod-2)*qp(bit[b],mod-2))%mod;
}
A>>=1;
if(A&1)
{
if(b&(1<<2)) res=(res+qp(bit[a],mod-2)*qp(bit[b],mod-2))%mod;
if(b&(1<<1)) res=(res+qp(bit[a],mod-2)*qp(bit[b],mod-2))%mod;
}
A>>=1;
if(A&1)
{
if(b&(1<<0)) res=(res+qp(bit[a],mod-2)*qp(bit[b],mod-2))%mod;
if(b&(1<<2)) res=(res+qp(bit[a],mod-2)*qp(bit[b],mod-2))%mod;
}
return res;
}
void run()
{
bit[0]=0;
for(int i=1;i<=7;i++) bit[i]=bit[i>>1]+(i&1);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>s[i];
//石头 剪刀 布
int res=0;
if(s[i][0]=='1') res+=(1<<0);
if(s[i][1]=='1') res+=(1<<1);
if(s[i][2]=='1') res+=(1<<2);
a[i]=res;
}
for(int i=1;i<=7;i++)
for(int j=1;j<=7;j++)
pre[i][j]=prebeat(i,j),suf[i][j]=sufbeat(i,j);
for(int i=n;i>=1;i--)
{
nums[i][a[i+1]]++;
for(int j=0;j<=7;j++)
{
nums[i][j]+=nums[i+1][j];
}
}
for(int j=0;j<=2;j++)
if(a[1]>>j&1) f[1][1<<j]=qp(bit[a[1]],mod-2);
ans[1]=0;
for(int j=0;j<3;j++)
{
if(a[1]>>j&1)
{
g[1][1<<j]=f[1][1<<j];
for(int k=1;k<8;k++)
{
if(nums[1][k])
{
g[1][1<<j]=(g[1][1<<j]*qp(suf[1<<j][k],nums[1][k]))%mod;
}
}
ans[1]+=g[1][1<<j];
ans[1]%=mod;
}
}
cout<<f[1][1<<0]<<' '<<f[1][1<<1]<<' '<<f[1][1<<2]<<'\n';
for(int i=2;i<=n;i++)
{
// for(int j=0;j<=2;j++)
// if(a[i]>>j&1) f[i][1<<j]=qp(bit[a[i]],mod-2);
// if(i==3)
// {
// cout<<f[i][1]<<' '<<f[i][2]<<' '<<f[i][4]<<'\n';
// }
for(int j=0;j<3;j++)
{
if(f[i-1][1<<j]!=0)
{
for(int k=0;k<3;k++)
{
if(a[i]>>k&1)
{
g[i][1<<k]=qp(bit[a[i]],mod-2);
//if(i==3) cout<<"j="<<j<<' '<<"k="<<k<<'\n';
//cout<<"cnm"<<f[i][1<<k]<<' '<<pre[1<<k][1<<j]<<' '<<f[i-1][1<<j]<<'\n';
f[i][1<<k]=(f[i][1<<k]+g[i][1<<k]*pre[1<<k][1<<j]%mod*f[i-1][1<<j]%mod)%mod;
}
}
}
}
// for(int j=0;j<3;j++)
// cout<<f[i][1<<j]<<' ';
// puts("");
// if(i==3)
// {
// cout<<f[i][1]<<' '<<f[i][2]<<' '<<f[i][4]<<'\n';
// }
for(int j=0;j<3;j++)
{
if(a[i]>>j&1)
{
g[i][1<<j]=f[i][1<<j];
for(int k=1;k<8;k++)
{
if(nums[i][k])
{
g[i][1<<j]=(g[i][1<<j]*qp(suf[1<<j][k],nums[i][k]))%mod;
}
}
ans[i]+=g[i][1<<j];
ans[i]%=mod;
}
}
for(int j=0;j<3;j++)
{
if(f[i-1][1<<j]!=0)
{
f[i][1<<j]=(f[i][1<<j]+suf[1<<j][a[i]]*f[i-1][1<<j]%mod)%mod;
// if(i==2) cout<<"j="<<j<<' '<<f[i][1<<j]<<'\n';
}
}
}
for(int i=1;i<=n;i++)
printf("%lld ",ans[i]);
puts("");
}
int main()
{
int T=1;
//scanf("%d",&T);
while(T--)
{
run();
}
return 0;
}
/*
吃早餐容易困 使得时间少容易困
*/
lpt的小屋 文章被收录于专栏
我想要一份甜甜的爱情
投递零跑科技等公司10个岗位 >
