ZR 集训 Day16 – 概率期望&生成函数

ooliver 发布于 5 小时前 47 次阅读 OI

AI 摘要

随机世界看似混沌，但期望与生成函数能将其驯服为优雅的算式。从条件概率到母函数，几个公式即可解开复杂难题。本文将带你走进这场确定性与随机性的奇妙交锋。

期望

  1. 定义：离散版本和连续版本，通常 OI 里用到的是离散的，也就是 $\mathbb{E}[X]=p_1 x_1+p_2 x_2+\dots+p_n x_n$
  2. 期望在任意条件下具有线性性，即 $\mathbb{E}[aX+Y]=a\mathbb{E}[X]+\mathbb{E}[Y]$
  3. 期望在无关的情况下可以相乘，即如果 $X,Y$ 无关，$\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$

条件概率

  1. 定义：$P(A|B)$ 是 $B$ 发生的情况下，$A$ 发生的概率
  2. $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<bits/stdc++.h>
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<(1<<n);i++){
        if(__builtin_popcount(i)!=r) continue;
        double now=1;
        for(int j=0;j<n;j++){
            if((i>>j)&1) now*=p[j];
            else now*=(1-p[j]);
        }
        for(int j=0;j<n;j++) if((i>>j)&1) ans[j]+=now;
        pb+=now;
    }
    for(int i=0;i<n;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;i<n;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<bits/stdc++.h>
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<=n;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;i<=id;i++){
        memset(dp,0,sizeof dp);
        memset(sum,0,sizeof sum);
        dp[0][m[i]]=1;
        for(int j=1;j<=k;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;l<=m[i];l++) dp[j][l]=sum[l];
        }
        int res=0;
        for(int j=0;j<=m[i];j++) (res+=(dp[k][j]*qpow(p[i],j))%mod)%=mod;
        (ans*=res)%=mod;
    }
    cout<<ans%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<bits/stdc++.h>
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;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(n<m) swap(n,m);
    init();
    for(int i=1;i<=m;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;
    cout<<ans;
    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<bits/stdc++.h>
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<=l;i++) for(int j=i;j<=n;j++) (a[j]+=a[j-i])%=mod;
    for(int i=1;i<=m-l+1;i++){
        cout<<a[n]<<"\n";
        for(int j=n;j>=i;j--) (a[j]=a[j]-a[j-i]+mod)%=mod;
        for(int j=i+l;j<=n;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<bits/stdc++.h>
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<bits/stdc++.h>
using namespace std;

#define int long long
#define lc p<<1
#define rc p<<1|1
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 f[20];
    void add(int v){
        sum=sum*v%mod;
        tag=tag*v%mod;
    }
}t[N<<2];

void pushup(int p){
    t[p].sum=(t[lc].sum+t[rc].sum)%mod;
}

void pushdown(int p){
    t[lc].add(t[p].tag);
    t[lc].val=t[lc].val*t[p].val%mod;
    t[rc].add(t[p].tag);
    t[rc].val=t[rc].val*t[p].val%mod;
    t[p].tag=t[p].val=1;
    for(int i=1;i<=cnt;i++){
        t[lc].f[i]+=t[p].f[i];
        t[rc].f[i]+=t[p].f[i];
        t[p].f[i]=0;
    }
}

void build(int p,int l,int r){
    t[p].l=l,t[p].r=r,t[p].tag=1,t[p].val=1;
    if(l==r){
        t[p].sum=a[l]%mod;
        int x=a[l];
        for(int i=1;i<=cnt;i++) while(x%prm[i]==0) t[p].f[i]++,x/=prm[i];
        t[p].val=x%mod;
        return;
    }
    int mid=(l+r)>>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<=r){
        t[p].add(val);
        for(int i=1;i<=cnt;i++) while(val%prm[i]==0) t[p].f[i]++,val/=prm[i];
        t[p].val=t[p].val*val%mod;
        return;
    }
    pushdown(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) mul(lc,l,r,val);
    if(r>mid) 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<=cnt;i++) while(x%prm[i]==0) t[p].f[i]--,x/=prm[i];
        t[p].sum=t[p].val=t[p].val*inv(x)%mod;
        for(int i=1;i<=cnt;i++) t[p].sum=t[p].sum*qpow(prm[i],t[p].f[i])%mod;
        return;
    }
    pushdown(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(pos<=mid) div(lc,pos,x);
    else div(rc,pos,x);
    pushup(p);
}

int query(int p,int l,int r){
    if(t[p].l>=l&&t[p].r<=r) return t[p].sum;
    pushdown(p);
    int mid=(t[p].l+t[p].r)>>1,sum=0;
    if(l<=mid) sum=(sum+query(lc,l,r))%mod;
    if(r>mid) 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;i<=v/i;i++){
        if(v%i) continue;
        prm[++cnt]=i;
        while(v%i==0) v/=i;
    }
    if(v>1) prm[++cnt]=v;
    for(int i=1;i<=n;i++) cin>>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<<query(1,l,r)%mod<<"\n";
    }
    return 0;
}