大户爱的硬币 HDU20260820B

WZH2026-08-202026-08-20

HDU20260820B 大户爱的硬币

第一道写出的计数题！！！！

题目描述：

一次抛硬币抛到正面的概率是 $p$ 。

求 $Var[X^k]$ ，其中 $Var[X]$ 表示随机变量的方差（即 $E[(X-E[X])^2]$ ）， $X$ 表示第一次抛硬币抛到正面的次数。结果对 $998244353$ 取模。

$0<p<998244352,k\le2\times10^5$ 。

看起来非常原题，且非常可以爆标。

首先， $Var[X]=E[X^2]-E[X]^2$ ，所以题目求的东西实际上是 $E[X^{2k}]-E[X^k]^2$ ，本质上是求 $E[X^k]$ 。

考虑斯特林反演，则由期望的线性性得原式为 $\sum\limits_{i=0}^k i!{k\brace{i}}E[\binom{X}{i}]$ 。

其中 $k\brace i$ 可以使用 FFT $\mathcal{O}(n\log n)$ 求出。所以问题变为求 $E[\binom{X}{i}]$ 。

考虑强行展开，得：

\begin{aligned} E[\binom{X}{i}]&=\sum_{j=1}^{\infty} p(1-p)^{j-1}\binom{j}{i}\\ &=p\sum_{j=0}^{\infty}(1-p)^j\binom{j+1}{i} \end{aligned}

不妨设 $F_i(x)$ 为 $\binom{j+1}{i}$ 的生成函数，那么就有 $E[\binom{X}{i}]=p\times F(1-p)$ 。

设 $G_i(x)$ 为 $\binom{j}{i}$ 的生成函数，那么就有 $F_i(x)=\frac{G_i(x)}{x}$ 。

然后：

\begin{aligned} G_i(x)&=\sum_{j=0}^{\infty}\binom{j}{i}x^j\\ &=\sum_{j=0}^{\infty}\binom{j-1}{i}x^j+\sum_{j=0}^{\infty}\binom{j-1}{i-1}x^j\\ &=x(G_{i-1}(x)+G_{i}(x))\\ \end{aligned}

解得 $G_i(x)=\frac{xG_{i-1}(x)}{1-x}$ ，边界条件 $G_0(x)=\frac{1}{1-x}$ 。

所以 $G_i(x)=\frac{x^{i-1}}{(1-x)^{i+1}}$ 。

然后代入计算即可。

复杂度 $\mathcal{O}(n\log n)$ 。（隔壁使用 $\mathcal{O}(n\log^2n)$ 的分治 FFT T 废了）。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1300010,P=998244353;
int R[N],fac[N],inv[N];
int kpow(int a,int b){
    int t=1;
    while(b){
        if(b&1)t=1ll*t*a%P;
        a=1ll*a*a%P;
        b>>=1;
    }
    return t;
}
void NTT(vector<int>&f,int t){
    int len=f.size();
    for(int i=0;i<len;i++)if(i<R[i])swap(f[i],f[R[i]]);
    for(int i=2;i<=len;i<<=1){
        int G=kpow(t==1?3:kpow(3,P-2),(P-1)/i);
        for(int j=0;j<len;j+=i){
            int g=1;
            for(int k=j;k<(j+(i>>1));k++){
                int x=f[k],y=1ll*g*f[k+(i>>1)]%P;
                f[k]=(x+y)%P;
                f[k+(i>>1)]=(x-y+P)%P;
                g=1ll*G*g%P;
            }
        }
    }
    if(t==-1){
        int in=kpow(len,P-2);
        for(int i=0;i<len;i++)f[i]=1ll*f[i]*in%P;
    }
}
void mul(vector<int>&x,vector<int>&y){
    int len=1,l=0;
    while(len<=(x.size()+y.size()-2))len<<=1,l++;
    for(int i=0;i<len;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(l-1));
    x.resize(len);y.resize(len);
    NTT(x,1);NTT(y,1);
    for(int i=0;i<len;i++)x[i]=1ll*x[i]*y[i]%P;
    NTT(x,-1);
}
vector<int> stiring(int n){
    vector<int>a(n+1),b(n+1);
    for(int i=0;i<=n;i++){
        a[i]=1ll*kpow(i,n)*inv[i]%P;
        b[i]=1ll*kpow(P-1,i)*inv[i]%P;
    }
    mul(a,b);
    a.resize(n+1);
    return a;
}
void WZH(){
    int k,p;
    scanf("%d%d",&k,&p);
    int q=(1-p+P)%P;
    vector<int>a=stiring(k);
    int ans=0,res=0;
    for(int i=0;i<=k;i++){
        int t=1ll*fac[i]*a[i]%P;
        if(i)t=1ll*t*kpow(q,i-1)%P*kpow(kpow(p,i),P-2)%P;
        (res+=t)%=P;
    }
    ans=(P-1ll*res*res%P)%P;
    a=stiring(2*k);
    for(int i=0;i<=2*k;i++){
        int t=1ll*fac[i]*a[i]%P;
        if(i)t=1ll*t*kpow(q,i-1)%P*kpow(kpow(p,i),P-2)%P;
        (ans+=t)%=P;
    }
    printf("%d\n",ans);
    return ;
}
int main(){
    fac[0]=1;
    for(int i=1;i<=400000;i++)fac[i]=1ll*i*fac[i-1]%P;
    inv[400000]=kpow(fac[400000],P-2);
    for(int i=400000-1;i>=0;i--)inv[i]=1ll*inv[i+1]*(i+1)%P;
    int T;
    scanf("%d",&T);
    while(T--)WZH();
    return 0;
}