UOJ449

（傳說中的$n^{2}k$做法）
首先強制鴿子飽的順序為$1?n$，最后答案乘$n!$即可
我們只需要考慮喂一次喂到了未飽的鴿子的情況，我們稱之為有效喂食
下一次喂食為有效喂食的概率為$\frac{n?x}{n}$，其中x為已經(jīng)飽了的鴿子數(shù)
所以兩次有效喂食之間的無效喂食次數(shù)的期望為$\frac{n}{n?x}$
這樣我們就消除了無效喂食的影響了
設(shè)$g[i][j]$表示已經(jīng)進行了$i$次有效喂食，$j$只鴿子已經(jīng)飽了的概率，$f[i][j]$表示期望
轉(zhuǎn)移有兩種情況：
1.下一次喂食沒有喂飽一只鴿子，這時概率就直接乘上$\frac{1}{n?x}$，期望加上當(dāng)前概率乘上無效喂食次數(shù)的期望
2.下一次喂食喂飽了一只鴿子，這時我們要從喂飽上一個鴿子之后的所有有效喂食中選出k-1個出來作為喂這只將要飽的鴿子的喂食，即$C_{i?j?k}^{k?1}$，轉(zhuǎn)移的時候就用情況1的轉(zhuǎn)移乘上這個系數(shù)即可

Code：

#include<bits/stdc++.h> #define mod 998244353 using namespace std; inline int read(){int res=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}return res*f; } const int N=105,K=5005; inline int add(int x,int y){x+=y;if(x>=mod) x-=mod;return x;} inline int dec(int x,int y){x-=y;if(x<0) x+=mod;return x;} inline int mul(int x,int y){return 1ll*x*y%mod;} inline void inc(int &x,int y){x+=y;if(x>=mod) x-=mod;} inline void Dec(int &x,int y){x-=y;if(x<0) x+=mod;} inline void Mul(int &x,int y){x=1ll*x*y%mod;} inline int ksm(int a,int b){int res=1;for(;b;b>>=1,a=mul(a,a)) if(b&1) res=mul(res,a);return res;} int fac[N*K],ifac[N*K]; int inv[N],p[N],e[N]; inline void init(int n,int k){fac[0]=fac[1]=ifac[0]=ifac[1]=1;for(int i=2;i<=n*k;i++) fac[i]=mul(fac[i-1],i);ifac[n*k]=ksm(fac[n*k],mod-2);for(int i=n*k-1;i;i--) ifac[i]=mul(ifac[i+1],i+1);inv[1]=1;for(int i=2;i<=n;i++) inv[i]=mul((mod-mod/i),inv[mod%i]);for(int i=0;i<=n;i++) p[i]=inv[n-i],e[i]=mul(n,inv[n-i]); } inline int C(int n,int m){if(n<0 || m<0 || n<m) return 0;return mul(fac[n],mul(ifac[m],ifac[n-m]));} int f[N*K][N],g[N*K][N]; int main(){int n=read(),k=read();init(n,k);f[0][0]=0,g[0][0]=1;for(int i=0;i<=n*k;i++)for(int j=0;j<=i/k;j++) if(g[i][j]){int P=mul(g[i][j],p[j]),E=add(mul(P,e[j]),mul(p[j],f[i][j])),Com=C(i-j*k,k-1);inc(f[i+1][j],E);inc(g[i+1][j],P);inc(f[i+1][j+1],mul(E,Com));inc(g[i+1][j+1],mul(P,Com));}cout<<mul(f[n*k][n],fac[n]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的[UOJ449][概率DP]集训队作业2018：喂鸽子的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。