牛客竞赛|牛客挑战赛59 B 游戏【dp】 c++|算法|acm竞赛

题目描述
有 n 个人玩石头剪刀布，分别编号为 1,2,??,n ，每个人在决定好要出什么手势后，整局游戏都只会出这种手势。
游戏进行 n?1 轮，第 1 轮由 1,2两人进行比赛，第 i(2≤i≤n?1) 轮由 i?1 轮的获胜者与第 i+1 个人进行比赛，胜利者根据如下规则判断：

【牛客竞赛|牛客挑战赛59 B 游戏【dp】】如果两人中一人出石头，一人出剪刀，则手势为石头的人获胜。
如果两人中一人出石头，一人出布，则手势为布的人获胜。
如果两人中一人出布，一人出剪刀，则手势为剪刀的人获胜。
否则如果两人手势一样，编号小的获胜。

你知道每个人可能决定要出的手势集合，并且每个人都会等概率地从自己的集合中选择一个手势，现在请你求出所有可能中每个人的获胜概率。
答案对 998244353 取模。
输入描述:

第一行一个整数 n (2≤n≤105) 表示人数。
接下来 n 行，第 iii 行输入一个长度为 3 的仅包含 01 的字符串 si?
若 si,1?=1 则第 i 个人的手势集合包含石头。
若 si,2?=1 则第 i 个人的手势集合包含剪刀。
若 si,3?=1 则第 i 个人的手势集合包含布。
数据保证 si? 中至少存在一个 1 。
输出描述: 一行输出 n 个数分别表示第 i 个人获胜的概率对 998244353 取模的结果。
一个有理数 P/Q 对一个质数模数 mod 取模的结果为 P×Q^mod?2
示例1
输入

4 010 111 111 001

输出 776412275 0 443664157 776412275
说明四个人获胜的概率分别为 4/9,0,1/9,4/9。
题解：
考虑 dp 出每个人有多少种情况会获胜。
设 dp[i][j] 表示前 i 个人，最后胜利的人一直出 j 的方案数。
设 dp1[i][j]表示后 i 个人，只出 j 的人能胜利的方案数。
转移比较显然，可以参考代码，时间复杂度 O(n)。
例如：此人出石头，那么前i个人是石头赢得概率有三种可能性，石头-石头，石头-剪刀（此人有剪刀才记），布-石头。而后几个人的只能全部石头和剪刀，只需要求后几个人出剪刀和石头的可能相乘即可。
AC代码：

#include using namespace std; #define sc(x) scanf("%d",&x) #define sl(x) scanf("%lld",&x) #define ll long long #define pb push_back typedef pairPII; const int Max=1e6+5; const ll INF=1e18+5; const ll mod=998244353; long long Power(long long base, long long power) { long long result = 1; while (power > 0) { if (power & 1) { result = result * base % mod; } power >>= 1; base = (base * base) % mod; } return result; } ll dp[Max][3]; ll dp1[Max][3]; ll vis[Max]; string s[Max]; int main(){ int n; sc(n); ll ans=1; string str; cin>>str; ll num=0; s[1]=str; dp[0][0]=1; dp[0][1]=1; dp[0][2]=1; for(int i=0; i<3; i++){ if(str[i]=='1') num++,dp[1][i]=1; } ans=num; string pre; for(int i=2; i<=n; i++){ cin>>str; num=0; s[i]=str; for(int j=0; j<3; j++){ if(str[j]=='1') num++; if(str[j]=='1'&&j==0){ dp[i][j]+=dp[i-1][1]; dp[i][j]%=mod; dp[i][j]+=dp[i-1][j]; dp[i][j]%=mod; dp[i][2]+=dp[i-1][2]; dp[i][2]%=mod; } else if(str[j]=='1'&&j==1){ dp[i][j]+=dp[i-1][2]; dp[i][j]%=mod; dp[i][j]+=dp[i-1][j]; dp[i][j]%=mod; dp[i][0]+=dp[i-1][0]; dp[i][0]%=mod; } else if(str[j]=='1'&&j==2){ dp[i][j]+=dp[i-1][0]; dp[i][j]%=mod; dp[i][j]+=dp[i-1][j]; dp[i][j]%=mod; dp[i][1]+=dp[i-1][1]; dp[i][1]%=mod; } pre=str; } ans*=num; ans%=mod; } ans=Power(ans,mod-2); dp1[n+1][0]=dp1[n+1][1]=dp1[n+1][2]=1; for(int i=n; i>=1; i--){ for(int j=0; j<3; j++){ if(j==0){ dp1[i][j]=dp1[i+1][j]*(s[i][j]-'0'+s[i][1]-'0'); dp1[i][j]%=mod; } else if(j==1){ dp1[i][j]=dp1[i+1][j]*(s[i][j]-'0'+s[i][2]-'0'); dp1[i][j]%=mod; } else if(j==2){ dp1[i][j]=dp1[i+1][j]*(s[i][j]-'0'+s[i][0]-'0'); dp1[i][j]%=mod; } } } dp[0][0]=dp[0][1]=dp[0][2]=1; dp1[n+1][0]=dp1[n+1][1]=dp1[n+1][2]=1; for(int i=1; i<=n; i++){ for(int j=0; j<3; j++){ if(s[i][j]=='1'&&j==0){ vis[i]+=(dp1[i+1][j])*dp[i-1][1]; vis[i]%=mod; } else if(s[i][j]=='1'&&j==1){ vis[i]+=(dp1[i+1][j])*dp[i-1][2]; vis[i]%=mod; } else if(s[i][j]=='1'&&j==2){ vis[i]+=(dp1[i+1][j])*dp[i-1][0]; vis[i]%=mod; } } vis[i]*=ans; vis[i]%=mod; } for(int i=1; i<=n-1; i++) printf("%lld ",vis[i]); printf("%lld\n",vis[n]); }