ZR 集训 Day16 - 概率期望&生成函数 · ooliver

期望定义：离散版本和连续版本，通常 OI 里用到的是离散的，也就是 \mathbb{E}[X]=p_1 x_1+p_2 x_2+\dots+p_n x_n 期望在任意条件下具有线性性，即 \mathbb{E}[aX+Y]=a\mathbb{E}[X]+\mathbb{E}[Y] 期望在无关的情况下可以相乘，即如果 X,Y 无关，\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y] 条件概率定义：P(A|B) 是 B 发生的情况下，A 发生的概率 P(A|B)=\frac{P(A和B都发生)}{P(B)} 生成函数生成函数（Generating function），又称母函数，是一种形式幂级数，通过其系数揭示序列信息。生成函数在组合数学和概率计算中扮演重要角色，广泛应用于解决组合问题和计算递推数列的通项公式。普通生成函数（OGF）对于一个序列 a，其普通生成函数为： F(x)=∑nanxnF(x)=\sum_{n} a_nx^n 指数生成函数（EGF）对于一个序列 a，其指数生成函数为： F(x)=∑nanxnn!F(x)=\sum_{n} a_n\frac{x^n}{n!} 区别 OGF 适合无编号物品，EGF 适合有编号物品。题单 UVA11181 条件概率 Probability|Given 可以说是条件概率模板题了。根据：P(A|B)=\frac{P(A和B都发生)}{P(B)}，我们只需要求出 i 选其余 n-1 个人选 r-1 个的概率再除以 n 个人里选 r 个的概率即可。由于 n 非常小，所以直接枚举状态即可。代码： C++ #include using namespace std; const int N=20; int n,r; double p[N],ans[N]; void solve(){ memset(ans,0,sizeof ans); double pb=0; for(int i=0;i>j)&1) now*=p[j]; else now*=(1-p[j]); } for(int j=0;j>j)&1) ans[j]+=now; pb+=now; } for(int i=0;i `#include using namespace std; const int N=20; int n,r; double p[N],ans[N]; void solve(){ memset(ans,0,sizeof ans); double pb=0; for(int i=0;i(1n);i++){ if(__builtin_popcount(i)!=r) continue; double now=1; for(int j=0;jn;j++){ if((i>>j)&1) now*=p[j]; else now*=(1-p[j]); } for(int j=0;jn;j++) if((i>>j)&1) ans[j]+=now; pb+=now; } for(int i=0;in;i++) printf("%0.6lf\n",ans[i]/pb); } signed main(){ int idx=0; while(++idx){ scanf("%d%d",&n,&r); if(n==0&&r==0) break; for(int i=0;in;i++) scanf("%lf",p+i); cout"Case "idx":\n"; solve(); } return 0; }` CF1097D Makoto and a Blackboard 不难发现，将 n 质因数分解为 \prod p_i^{m_i} 后，每次操作对于不同的 p_i^{m_i} 都是独立的，所以我们可以分质因数求期望，最后乘在一起。换句话说，答案是具有积性的。对于每个质因数，我们考虑 DP，设 dp_{i,j} 表示进行 i 次操作后指数为 j 的概率，可以得到： dpi,j=∑k=jmdpi−1,kk+1dp_{i,j}=\sum_{k=j}^{m} \frac{dp_{i-1,k}}{k+1} 后缀和优化即可。代码： C++ #include using namespace std; #define int long long const int mod=1e9+7; int n,k,id,ans=1; int p[100],m[100],sum[100],dp[10005][100]; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } signed main(){ cin>>n>>k; int x=n; for(int i=2;i*i=0;l--) sum[l]=(sum[l+1]+dp[j-1][l]*qpow(l+1,mod-2))%mod; for(int l=0;l `#include using namespace std; #define int long long const int mod=1e9+7; int n,k,id,ans=1; int p[100],m[100],sum[100],dp[10005][100]; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } signed main(){ cin>>n>>k; int x=n; for(int i=2;i*in;i++){ if(x%i) continue; p[++id]=i; while(x%i==0) m[id]++,x/=i; } if(x!=1) p[++id]=x,m[id]=1; for(int i=1;iid;i++){ memset(dp,0,sizeof dp); memset(sum,0,sizeof sum); dp[0][m[i]]=1; for(int j=1;jk;j++){ for(int l=m[i];l>=0;l--) sum[l]=(sum[l+1]+dp[j-1][l]*qpow(l+1,mod-2))%mod; for(int l=0;lm[i];l++) dp[j][l]=sum[l]; } int res=0; for(int j=0;jm[i];j++) (res+=(dp[k][j]*qpow(p[i],j))%mod)%=mod; (ans*=res)%=mod; } coutans%mod; return 0; }` AT_agc019_f [AGC019F] Yes or No 最优策略很好想，肯定是猜个数更多的那个答案，所以保底我们有 \max(n,m) 的答案。但是，期望还会在 n=m 时增加，如果这个时候我们蒙对了，max(n,m) 不会改变，但是答案加了 1，也就是对期望产生了 \frac{1}{2} 的贡献。这是我们把问题抽象成在坐标系中从 (n,m) 走到 (0,0) 的问题，每走到 (i,i) 就会额外加上 \frac{1}{2} 的贡献。所以我们枚举 (i,i)，将答案加上经过这个点的概率乘上 \frac{1}{2}，最后再加上 max(n,m) 的保底答案。代码： C++ #include using namespace std; #define int long long const int N=1e6+5; const int mod=998244353; int n,m,ans; int jie[N],inv[N]; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } void init(){ jie[0]=inv[0]=1; for(int i=1;i>n>>m; if(n `#include using namespace std; #define int long long const int N=1e6+5; const int mod=998244353; int n,m,ans; int jie[N],inv[N]; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } void init(){ jie[0]=inv[0]=1; for(int i=1;in+m;i++){ (jie[i]=jie[i-1]*i)%=mod; inv[i]=qpow(jie[i],mod-2); } } int chose(int x,int y){ return ((jie[x]*inv[y])%mod*inv[x-y])%mod; } signed main(){ cin>>n>>m; if(nm) swap(n,m); init(); for(int i=1;im;i++) (ans+=chose(m+n-2*i,n-i)*chose(2*i,i)%mod)%=mod; (ans*=qpow(chose(m+n,n),mod-2))%=mod; (ans*=qpow(2,mod-2))%=mod; (ans+=n)%=mod; coutans; return 0; }` AT_fps_24_g 硬貨生成函数题。设当前答案的生成函数为 A(x)，考虑两种操作：添加硬币和移除硬币。对于添加硬币 p，相当于对答案函数乘上 \sum_{i=0} x^{ip}，即 \frac{1}{1-x^p}。此时就有： A′(x)=A(x)⋅11−xpA(x)=A′(x)⋅(1−xp)∑i=0aixi=∑i=0ai′xi−∑i=0ai′xi+p∴ai=ai′−ai−p′ai′=ai+ai−p′\begin{aligned} A'(x)&=A(x)\cdot \frac{1}{1-x^p} \ A(x)&=A'(x)\cdot (1-x^p) \ \sum_{i=0} a_ix^i&=\sum_{i=0} a'ix^i - \sum{i=0} a'_ix^{i+p} \ \therefore a_i&=a'i-a'{i-p} \ a'i&=a_i+a'{i-p} \end{aligned} 从小到大更新即可。对于删除一个硬币，无非就是对如上操作进行逆操作，即乘上 1-x^p，式子不推了，是同理的。代码： C++ #include using namespace std; #define int long long const int N=1e6+5; const int mod=998244353; int n,m,l; int a[N]; signed main(){ cin>>n>>m>>l; a[0]=1; for(int i=1;i=i;j--) (a[j]=a[j]-a[j-i]+mod)%=mod; for(int j=i+l;j `#include using namespace std; #define int long long const int N=1e6+5; const int mod=998244353; int n,m,l; int a[N]; signed main(){ cin>>n>>m>>l; a[0]=1; for(int i=1;il;i++) for(int j=i;jn;j++) (a[j]+=a[j-i])%=mod; for(int i=1;im-l+1;i++){ couta[n]"\n"; for(int j=n;j>=i;j--) (a[j]=a[j]-a[j-i]+mod)%=mod; for(int j=i+l;jn;j++) (a[j]+=a[j-i-l])%=mod; } return 0; }` AT_fps_24_f 色紙同样的生成函数题目，但是发现这道题是需要考虑编号的，也就是所涂的颜色，于是使用指数生成函数。红、蓝、黄三个颜色的指数生成函数如下： R(x)=∑ixii!=exB(x)=∑ix2i(2i)!=ex+e−x2Y(x)=∑ix2i+1(2i+1)!=ex−e−x2\begin{aligned} R(x)&=\sum_{i} \frac{x^i}{i!} = e^x \ B(x)&=\sum_{i} \frac{x^{2i}}{(2i)!} = \frac{e^x+e^{-x}}{2} \ Y(x)&=\sum_{i}\frac{x^{2i+1}}{(2i+1)!} = \frac{e^x-e^{-x}}{2} \ \end{aligned} 则答案的生成函数为： F(x)=R(x)B(x)Y(x)=e3x−e−x4=∑i(3x)ii!−∑i(−x)ii!4=∑i3ixii!−∑i(−1)ixii!4=∑i3i−(−1)i4xii!\begin{aligned} F(x)&=R(x)B(x)Y(x) \ &= \frac{e^{3x}-e^{-x}}{4} \ &= \frac{\sum_{i} \frac{(3x)^i}{i!}-\sum_{i} \frac{(-x)^i}{i!}}{4} \ &= \frac{\sum_{i} 3^i\frac{x^i}{i!}-\sum_{i} (-1)^i\frac{x^i}{i!}}{4} \ &= \sum_{i} \frac{3^i-(-1)^i}{4}\frac{x^i}{i!} \end{aligned} 则答案：[x^n]F(x)=\**frac**{3^i-(-1)^i}{4}。代码： C++ #include using namespace std; #define int long long const int mod=998244353; int n; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } signed main(){ cin>>n; cout `#include using namespace std; #define int long long const int mod=998244353; int n; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } signed main(){ cin>>n; cout((qpow(3,n)+(n&1?1:mod-1))%mod*qpow(4,mod-2))%mod; return 0; }` CF1109E Sasha and a Very Easy Test 用线段树维护区间和，每个节点记录与模数互质部分的值、质因子指数的懒标记以及区间乘法标记。区间乘时将乘数分离后分别更新；单点除时对除数分离后指数相减、互质部分乘逆元，再合并得到新值。总时间复杂度 O((n+q)\log n \cdot \omega(mod))，其中 \omega(mod) 为模数的不同质因子个数（不超过 9），足以通过本题。代码： C++ #include using namespace std; #define int long long #define lc p>=1; } return res; } int exgcd(int a,int b,int &x,int &y){ if(!b){ x=1,y=0; return a; } int gcd=exgcd(b,a%b,x,y); int t=x; x=y,y=t-a/b*y; return gcd; } int inv(int u){ int x,y; exgcd(u,mod,x,y); return (x%mod+mod)%mod; } struct tree{ int l,r,val,sum,tag; int f[20]; void add(int v){ sum=sum*v%mod; tag=tag*v%mod; } }t[N>1; build(lc,l,mid); build(rc,mid+1,r); pushup(p); } void mul(int p,int l,int r,int val){ if(t[p].l>=l&&t[p].r>1; if(lmid) mul(rc,l,r,val); pushup(p); } void div(int p,int pos,int x){ if(t[p].l==t[p].r){ for(int i=1;i>1; if(pos=l&&t[p].r>1,sum=0; if(lmid) sum=(sum+query(rc,l,r))%mod; return sum; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>mod; int v=mod; for(int i=2;i1) prm[++cnt]=v; for(int i=1;i>a[i]; build(1,1,n); cin>>m; while(m--){ int op,l,r,x; cin>>op>>l>>r; if(op==1) cin>>x,mul(1,l,r,x); if(op==2) div(1,l,r); if(op==3) cout `#include using namespace std; #define int long long #define lc p #define rc p const int N=1e5+5; int n,mod,cnt,m; int a[N],prm[20]; int qpow(int x,int y){ int res=1; while(y){ if(y&1) (res*=x)%=mod; (x*=x)%=mod,y>>=1; } return res; } int exgcd(int a,int b,int &x,int &y){ if(!b){ x=1,y=0; return a; } int gcd=exgcd(b,a%b,x,y); int t=x; x=y,y=t-a/b*y; return gcd; } int inv(int u){ int x,y; exgcd(u,mod,x,y); return (x%mod+mod)%mod; } struct tree{ int l,r,val,sum,tag; int…