CF932E
jijidawang
·
·
题解
首先根据观察可以知道
\dfrac1{2^{n-k}}\sum_{i=0}^n\dbinom nii^k
是关于 n 的 k 次多项式 .
证明如下：
答案肯定是关于 n 的多项式，下面分析次数 .
根据经典思路，令 \displaystyle f_{k,n}(z)=\sum_{i=1}^n\dbinom nii^kz^i=g_{k,n}(z)\cdot(z+1)^{n-k}，其中 g_{k,n} 是一关于 n 的多项式 .
\begin{aligned}\dfrac{\mathrm d}{\mathrm dz}(f_{k,n}(z)z)&=f_{k,n}(z)+zf'_{k,n}(z)\\&=g_{k,n}(z)\cdot(z+1)^{n-k}+z(g_{k,n}'(z)\cdot(z+1)^{n-k}+(n-k)g_{k,n}(z)\cdot(z+1)^{n-k-1})\\&=g_{k,n}(2)2^{n-k}+2(g'_{k,n}(z)2^{n-k}+(n-k)g_{k,n}(2)2^{n-k-1})\\&=(n-k+1)g_{k,n}(2)2^{n-k}+2g'_{k,n}(2)2^{n-k}\\&=2^{n-k}((n-k+1)g_{k,n}(2) + 2g'_{k,n}(2))\end{aligned}
第三个等号处代入 z=1 .
归纳即可得到为 k 次 .
于是暴力 \Theta(k^2) 求点值后 Lagrange 插值即可，时间复杂度 \Theta(k^2) .