题目
$laofu $出的题
(n)个离散型随机变量(X_i)可能的值为([1,D]) ,求有至少(m)对的概率
$0 le m le 10^9 , 1 le n le 10^9 , 1 le D le 10^5 $
题解
-
60 pts
观察到能配对的个数只和颜色奇数个数有关
令(L=min(D,n-2m))，这是奇数个数上界
(dp_i,j)表示前(i)个球，奇数个数为(j)的方案
复杂度:(O(Dn))
如果用快速幂转移加上一些奇技淫巧可以通过13-15
-
100pts
$ f_i $ 表示硬点$ i $ 个颜色是奇数的方案和
[egin{align} f_i &= (^D_i)n^i e^{(D-i)x}\ &= frac{i!(^D_i)}{2^i} sum_{j=0}^{i} frac{(-1)^j(D-2j)^n}{j!(i-j)!} end{align} ]直接把(f_i)卷出来，考虑二项式反演
[egin{align} g_i &= sum_{j ge i}(-1)^{j-i}(^j_i) f_j \ 即 i!g_i &= sum_{j ge i}frac{(-1)^{j-i}}{(j-i)!} imes j!f_j\ 把 G和F都 & reverse 一下就可以卷积了 end{align} ]#include<bits/stdc++.h> #define ll long long #define mod 998244353 using namespace std; const int N=400010; int D,n,m,G=3,fac[N],inv[N],ny[N],len,L,rev[N],a[N],b[N],c[N],f[N]; void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;} int pw(int x,int y){ if(y<0)y+=mod-1; int re=1; while(y){ if(y&1)re=(ll)re*x%mod; y>>=1;x=(ll)x*x%mod; } return re; } void ntt(int*A,int F){ for(int i=0;i<len;++i)if(i<rev[i])swap(A[i],A[rev[i]]); for(int i=1;i<len;i<<=1){ int wn=pw(G,F*(mod-1)/i/2); for(int j=0;j<len;j+=(i<<1)){ int w=1; for(int k=0;k<i;++k,w=(ll)w*wn%mod){ int x=A[j+k],y=(ll)w*A[j+k+i]%mod; A[j+k]=(x+y)%mod;A[j+k+i]=(x-y+mod)%mod; } } } if(!~F)for(int i=0;i<len;++i)A[i]=(ll)ny[len]*A[i]%mod; } void Mul(int*A,int*B,int*C){ ntt(A,1);ntt(B,1); for(int i=0;i<len;++i)C[i]=(ll)A[i]*B[i]%mod; ntt(C,-1); } int main(){ // freopen("pearl.in","r",stdin); // freopen("pearl.out","w",stdout); scanf("%d%d%d",&D,&n,&m); for(L=0,len=1;len<=D<<1;++L,len<<=1); ny[1]=1;for(int i=2;i<=len;++i)ny[i]=(ll)(mod-mod/i)*ny[mod%i]%mod; for(int i=fac[0]=inv[0]=1;i<=len;++i){ fac[i]=(ll)fac[i-1]*i%mod; inv[i]=(ll)inv[i-1]*ny[i]%mod; rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1)); } for(int i=0;i<=D;++i){ f[i]=(ll)fac[D]*inv[D-i]%mod*pw(2,-i)%mod; b[i]=(ll)inv[i]*pw((D-2*i+mod)%mod,n)%mod; a[i]=inv[i];if(i&1)b[i]=(mod-b[i])%mod; } Mul(a,b,c); for(int i=0;i<=D;++i)f[i]=(ll)f[i]*c[i]%mod; for(int i=0;i<len;++i)a[i]=b[i]=c[i]=0; for(int i=0;i<=D;++i){ a[i]=i&1?mod-inv[i]:inv[i]; b[i]=(ll)fac[D-i]*f[D-i]%mod; } Mul(a,b,c); int ans=0,mn=min(D,n-2*m); for(int i=0;i<=mn;++i)inc(ans,(ll)inv[i]*c[D-i]%mod); cout<<ans<<endl; return 0; } -
官解
感觉挺好玩
谁说生成函数只能有一个未知数的？？？
我们重新设计一下不用二项式反演的生成函数
[egin{align} ans &= sum_{i=0}^{L}n!(frac{e^x+e^{-x}}{2}+yfrac{e^x-e^{-x}}{2})^D[x^ny^i]\ &= frac{n!}{2^D} sum_{i=0}^{L}(e^x(1+y)+e^{-x}(1-y))^D[x^ny^i]\ &= frac{n!}{2^D} sum_{i=0}^{L}sum_{j=0}^{D}(^D_j)e^{(2j-D)x}(1+y)^j(1-y)^{D-j}[x^ny^i]\ &= frac{n!}{2^D} sum_{j=0}^{D}(^D_j)e^{(2j-D)x}[x^n] sum_{i=0}^{L}(1+y)^j(1-y)^{D-j}[x^ny^i]\ end{align} ]考虑求后面(y)那坨，就是某个式子的前(L)项和，我们知道：
[(1+y)^i(1-y)^{D-i} = -(1+y)^{i-1}(1-y)^{D-i+1}+2(1+y)^{i-1}(1-y)^{D-i}\
即F(D,i) = -F(D,i-1) + 2F(D-1,i-1)
]
只需要求出(F(I,0)(I le D))即可通过组合数卷出(F(D,i))
可是由于我上课没有认真听讲，所以我忘了怎么求的(F(I,0))惹．．．．．．．
可能有天会突然醒悟吧．．．．
upd:看了上课认真听讲的BAJim_H的题解，好吧是我太弱了．．．．．
[egin{align}
F(I,0)&= egin{cases}
0 &(I>L)\
sum_{i=0}^{L} (-1)^i (^I_i) &(I<L)
end{cases}\
&讨论第二个式子，把组合数拆开\
&= sum_{i=0}^{L} (^{I-1}_i)(-1)^i + sum_{i=0}^{L-1}(^{L-1}_{i})(-1)^{i+1}\
&= (^{I-1}_L)(-1)^L
end{align}
]
这样只要一次卷积．