題目描述

有一道選擇題，有 a,b,c,d 四個選項。

現在有 n 個人來做這題，第 i 個人有 pi,j 的概率選第 j 個選項。

定義\(cnt(x)\)為選第$ x $個選項的人數。

令\(mx\)為\(cnt(x)\)最大的\(x\)(如果有多個\(cnt(x)\)最大的$ x$，則取其中 \(x\) 最小的)，若 ，則所有人得 \(0\) 分；否則令 choicei 表示第$ i $個人選的選項，則第 i 人得 分。

求每個人的期望得分。

輸入描述:

第一行一個整數 n ，表示人數。

接下來 n 行，每行 4 個整數，其中第 \(i\) 行第 \(j\) 個數表示 \(p_{i,j}\) ，即在模 \(998244353\) 意義下第 i 個人選第 j 個選項的概率。

接下來 4 行，每行 4 個整數，第 \(i\) 行第 \(j\) 個數表示 \(w_{i,j}\) 。

輸出描述:

共 n 行，第 i 行表示第 i 個人在模 \(998244353\) 意義下的期望得分。

示例1

輸入

2 499122177 499122177 0 0 332748118 665496236 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

輸出

166374061 166374061

說明

第一個人選第 1,2,3,4 個選項的概率分別為 ；

第二個人選第 1,2,3,4 個選項的概率分別為 。

當他們選擇不同選項時， ，所有人得分為 \(0\) ；

當他們都選第 1 個選項時，概率為 (1/2)*(1/3)=1/6，兩個人的得分都是 \(w_{1,1}=1\)；

當他們都選第 2 個選項時，概率為 ，兩個人的得分都是 \(w_{2,2}=6\) 。

所以兩個人的期望得分都是 ， 模 \(998244353=166374061\) 。

Solution

首先循環枚舉每個選項\(a\)。

我們設\(f[i][j]\)表示前\(i\)個人有\(j\)人選了這個選項的概率，\(g[i][j]\)表示后\(i\)個人有\(j\)人選了這個選項的概率。轉移是很顯然的吧。

\[f[i][j]=f[i-1][j-1]\times p[i][a]+f[i-1][j]\times (1-p[i][a])\quad f[0][0]=1\]

\[g[i][j]=g[i+1][j-1]\times p[i][a]+g[i+1][j]\times (1-p[i][a])\quad g[n+1][0]=1\]

然后我們考慮對\(g\)的第二維做個后綴和或者對\(f\) 的第二維做個前綴和。我們拿做\(g\)來說。那么\(g[i][j]\)的意義就變成了后\(i\)個人，選了這個選項的人數不少于\(j\)個的概率。

然后枚舉每一個人，對每一個人，再枚舉這個人前面有多少人選這一項，然后下面就不用再說了吧，非常顯然的搞一下就好了。

#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; #define lowbit(x) ((x)&(-(x))) #define REP(i,a,n) for(register int i=(a);i<=(n);++i) #define PER(i,a,n) for(register int i=(a);i>=(n);--i) #define FEC(i,x) for(register int i=head[x];i;i=g[i].ne) template<typename A>inline void read(A&a){a=0;char c=0;int f=1;while(c<'0'||c>'9')(c=getchar())=='-'?f=-1:0;while(c>='0'&&c<='9')a=(a<<3)+(a<<1)+c-'0',c=getchar();f==-1?a=-a:0;} char buf[30];template<typename A>inline void write(A a){if(a<0)putchar('-'),a=-a;int top=0;if(!a)buf[top=1]='0';while(a)buf[++top]=a%10+'0',a/=10;while(top)putchar(buf[top--]);} typedef long long ll;typedef unsigned long long ull; template<typename A,typename B>inline bool SMAX(A&x,const B&y){return y>x?x=y,1:0;} template<typename A,typename B>inline bool SMIN(A&x,const B&y){return y<x?x=y,1:0;}const int N=2000+7,MOD=998244353; int n,m,p[N][4],w[4][4],f[N][N],g[N][N],ans[N]; template<typename A,typename B>inline void SADD(A&x,const B&y){x+=y;x>=MOD?x-=MOD:0;}int main(){read(n);m=(n>>1)+1;for(register int i=1;i<=n;++i)read(p[i][0]),read(p[i][1]),read(p[i][2]),read(p[i][3]);for(register int i=0;i<4;++i)read(w[i][0]),read(w[i][1]),read(w[i][2]),read(w[i][3]);for(register int c=0;c<4;++c){memset(f,0,sizeof(f));memset(g,0,sizeof(g));f[0][0]=1;g[n+1][0]=1;for(register int i=1;i<=n;++i)for(register int j=0;j<=i;++j)f[i][j]=((j?(ll)f[i-1][j-1]*p[i][c]%MOD:0)+(ll)f[i-1][j]*(MOD+1-p[i][c])%MOD)%MOD;for(register int i=n;i;--i)for(register int j=0;j<=n-i+1;++j)g[i][j]=((j?(ll)g[i+1][j-1]*p[i][c]%MOD:0)+(ll)g[i+1][j]*(MOD+1-p[i][c])%MOD)%MOD;for(register int i=1;i<=n;++i)for(register int j=n-i;~j;--j)SADD(g[i][j],g[i][j+1]);for(register int i=1;i<=n;++i){for(register int j=0;j<=i;++j)for(register int k=0;k<4;++k)SADD(ans[i],(ll)f[i-1][j]*g[i+1][m-j-(k==c)>=0?m-j-(k==c):0]%MOD*p[i][k]%MOD*w[c][k]%MOD);}}for(register int i=1;i<=n;++i)write(ans[i]),putchar('\n'); }

轉載于:https://www.cnblogs.com/hankeke/p/nowcoder-noiptg6-B.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的牛客网NOIP赛前集训营-提高组（第六场）B-选择题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。