經典數數題

「PKUWC2018」獵人殺

• 咱們硬點一個集合在 1 後面死而後容斥
  考慮每次在 $[1,n]$ 隨機，若是不在集合 $S$ 中就跳過，那麼每一個人死亡的機率是同樣的，證實以下
  $\frac{w_t} {\sum_{i\in S}w_i}=\frac{w_t}{\sum_{i=1}^nw_i}(\sum_{i\ge0}(\frac{\sum_{j=1}^nw_j-\sum_{j\in S}w_j}{\sum_{j=1}^nw_j})^i)$
  分治 $ntt$ 算一下大小爲 $Sum$ 的集合個數（帶容斥係數）

【集訓隊做業2018】喂鴿子

• 考慮 $min-max$ 容斥，咱們對一個集合 $S$ 求出它當中第一個餵飽的指望，假設第一個餵飽的時間爲 $t$，咱們用方案數除以總方案即 $|S|^t$ 就能夠獲得指望，方案數寫成 $egf$ 的形式就是（咱們欽定一個最早飽，那麼總方案乘上 $|S|$ 便可）
  $t![x^t]\frac{x^k}{(k-1)!}(\sum_{i=0}^{k-1}\frac{x^i}{i!})^{|S|-1}*\frac{1}{|S|^t}*\frac{n*t}{|S|}*|S|$
  注意到 $f^t(x)=(\sum_{i=0}^{k-1}\frac{x^i}{i!})^t$ 是能夠遞推的
  $f^t(x)'=tf^{t-1}(x)(f(x)-\frac{x^{k-1}}{(k-1)!})\\ (n+1)[x^{n+1}]f^t(x)=t[x^n]f^t(x)-t[x^{n-k+1}]\frac{f^{t-1}(x)}{(k-1)!}$
  $O(n^2k)$

【UR #19】通用測評號

• 考慮對一個點統計它滿了存在一個其它沒有滿的機率，最後乘上 $n$ 便可
  咱們硬點一個集合 $S$，求出這個點滿了其它的都沒有滿的機率最後容斥，寫成 $egf$ 的形式就是
  $(t+a-1)![x^{t+a}]\frac{x^a}{(a-1)!}(\sum_{i=0}^{b-1}\frac{x^i}{i!})^{|S|}\frac{1}{(|S|+1)^{t+a}}$
  $O(n^3)$