題意

有n只鴿子，每個時刻會等概率隨機給某只鴿子喂食，若一只鴿子被喂食的次數不小于k次則已飽。問期望多少個時刻之后每只鴿子都已飽。
$n\le 50,k\le 1000$

分析

先min-max容斥一下轉成求$E(min(t_i))$。
然后問題變成求前m個盒子恰好有一個被放了k個球的期望時間。
設這m個盒子總共放了x個球，那么到達某個合法狀態的期望時間就是$\frac{x}{\frac{m}{n}}$，概率是$\frac{1}{m^x}$，這就變成了一個計數題，用FFT優化一下就好。
時間復雜度$O(n^{2}klog(nk))$。

代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm>typedef long long LL;const int N=55; const int M=1005; const int MOD=998244353;int n,m,f[N][N*M],jc[N*M],ny[N*M],a[N*M*2],b[N*M*2],T,rev[N*M*2];int ksm(int x,int y) {int ans=1;while (y){if (y&1) ans=(LL)ans*x%MOD;x=(LL)x*x%MOD;y>>=1;}return ans; }void NTT(int *a,int f) {for (int i=0;i<T;i++) if (i<rev[i]) std::swap(a[i],a[rev[i]]);for (int i=1;i<T;i<<=1){int wn=ksm(3,f==1?(MOD-1)/i/2:MOD-1-(MOD-1)/i/2);for (int j=0;j<T;j+=i*2){int w=1;for (int k=0;k<i;k++){int u=a[j+k],v=(LL)a[j+k+i]*w%MOD;a[j+k]=(u+v)%MOD;a[j+k+i]=(u-v)%MOD;w=(LL)w*wn%MOD;}}}int t=ksm(T,MOD-2);if (f==-1) for (int i=0;i<T;i++) a[i]=(LL)a[i]*t%MOD; }void work() {f[0][0]=1;for (int i=0;i<m;i++) f[1][i]=ny[i];int now=m-1;for (int i=2;i<=n;i++){int lg=0;for (T=1;T<=now+m-1;T<<=1,lg++);for (int j=0;j<T;j++) rev[j]=(rev[j>>1]>>1)|((j&1)<<(lg-1)),a[j]=b[j]=0;for (int j=0;j<=now;j++) a[j]=f[i-1][j];for (int j=0;j<m;j++) b[j]=ny[j];NTT(b,1);NTT(a,1);for (int j=0;j<T;j++) a[j]=(LL)b[j]*a[j]%MOD;NTT(a,-1);now+=m-1;for (int j=0;j<=now;j++) f[i][j]=a[j];} }int main() {scanf("%d%d",&n,&m);jc[0]=jc[1]=ny[0]=ny[1]=1;for (int i=2;i<=n*m;i++) jc[i]=(LL)jc[i-1]*i%MOD,ny[i]=(LL)(MOD-MOD/i)*ny[MOD%i]%MOD;for (int i=2;i<=n*m;i++) ny[i]=(LL)ny[i-1]*ny[i]%MOD;work();int ans=0;for (int i=1;i<=n;i++){int tot=0,w=0,t=ksm(i,MOD-2),h=ksm(t,m);for (int j=m;j<=i*(m-1)+1;j++){(w+=(LL)f[i-1][j-m]*i%MOD*ny[m-1]%MOD*jc[j-1]%MOD*n%MOD*j%MOD*t%MOD*h%MOD)%=MOD;h=(LL)h*t%MOD;}w=(LL)w*jc[n]%MOD*ny[i]%MOD*ny[n-i]%MOD;if (i&1) (ans+=w)%=MOD;else (ans-=w)%=MOD;}ans+=ans<0?MOD:0;printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的UOJ #449.【集训队作业2018】喂鸽子 min-max容斥的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。