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

2026年8月1日 ooliver OI

期望

定义：离散版本和连续版本，通常 OI 里用到的是离散的，也就是 $E [X] = p_{1} x_{1} + p_{2} x_{2} + [PARSE ERROR: Undefined("Command(\"dots\")")] + p_{n} x_{n}$
期望在任意条件下具有线性性，即 $E [a X + Y] = a E [X] + E [Y]$
期望在无关的情况下可以相乘，即如果 $X, Y$ 无关， $E [X Y] = E [X] 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，设 $d p_{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$ 时增加，如果这个时候我们蒙对了， $m a x (n, m)$ 不会改变，但是答案加了 $1$ ，也就是对期望产生了 $\frac{1}{2}$ 的贡献。这是我们把问题抽象成在坐标系中从 $(n, m)$ 走到 $(0, 0)$ 的问题，每走到 $(i, i)$ 就会额外加上 $\frac{1}{2}$ 的贡献。所以我们枚举 $(i, i)$ ，将答案加上经过这个点的概率乘上 $\frac{1}{2}$ ，最后再加上 $m a x (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^{i p}$ ，即 $\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) = [PARSE ERROR: Undefined("Command(\"*\")")] * f r a c * * 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 ω (m o d))$ ，其中 $ω (m o d)$ 为模数的不同质因子个数（不超过 $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 f[20];
    void add(int v){
        sum=sum*v%mod;
        tag=tag*v%mod;
    }
}t[N2];

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;icnt;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;icnt;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].rr){
        t[p].add(val);
        for(int i=1;icnt;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(lmid) 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;icnt;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;icnt;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(posmid) 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].rr) return t[p].sum;
    pushdown(p);
    int mid=(t[p].l+t[p].r)>>1,sum=0;
    if(lmid) 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;iv/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;in;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) coutquery(1,l,r)%mod"\n";
    }
    return 0;
}`