给定 m , n , p , f ( 1 ) , … , f ( m ) m,n,p,f(1),\dots,f(m) m,n,p,f(1),…,f(m)，求出 ∑ i = 0 n f ( i ) ( n i ) p i ( 1 − p ) n − i \sum_{i=0}^nf(i)\binom{n}{i}p^i(1-p)^{n-i} i=0∑nf(i)(in)pi(1−p)n−i G F \mathcal{GF} GF 告诉我们一种很优雅的方式： ∑ c t [ z t ] ( p e z + 1 − p ) n \sum c_t[z^t](pe^z+1-p)^n ∑ct[zt](pez+1−p)n 是很优美，但是给点值很不友好 注意到后面一坨就是二项分布 考虑其母函数 g X ( z ) = ∑ k ≥ 0 Pr [ X = k ] z k g_X(z)=\sum_{k\ge 0}\text{Pr}[X=k]z^k gX(z)=∑k≥0Pr[X=k]zk 在这里 g X ( z ) = ∑ k ≥ 0 ( n k ) p i ( 1 − p ) n − i z i = ( p z + 1 − p ) n g_X(z)=\sum_{k\ge 0}\binom{n}{k}p^i(1-p)^{n-i}z^i=(pz+1-p)^n gX(z)=∑k≥0(kn)pi(1−p)n−izi=(pz+1−p)n 我们知道 g ( k ) ( 1 ) = E [ X k ‾ ] g^{(k)}(1)=\text{E}[X^{\underline k}] g(k)(1)=E[Xk] 所以说 ∑ i = 0 n i t ‾ ( n i ) p i ( 1 − p ) n − i = E [ X t ‾ ] = ( p z + 1 − p ) n − k n k ‾ p k ∣ z = 1 = n k ‾ p k \sum_{i=0}^ni^{\underline t}\binom{n}{i}p^i(1-p)^{n-i}=\text{E}[X^{\underline t}]=(pz+1-p)^{n-k}n^{\underline k}p^k\Big|_{z=1}=n^{\underline k}p^k i=0∑nit(in)pi(1−p)n−i=E[Xt]=(pz+1−p)n−knkpk∣∣∣z=1=nkpk 当然也可以直接推 ∑ i i t ‾ ( n i ) p i ( 1 − p ) n − i = ∑ i ≥ t n t ‾ ( n − t i − t ) p i ( 1 − p ) n − i = n t ‾ p t \sum _ii^{\underline t}\binom{n}{i}p^i(1-p)^{n-i}\\=\sum_{i\ge t}n^{\underline t}\binom{n-t}{i-t}p^i(1-p)^{n-i}=n^{\underline t}p^t ∑iit(in)pi(1−p)n−i=∑i≥tnt(i−tn−t)pi(1−p)n−i=ntpt 不过题目希望你优雅地求和
