[NCT058D]大水题

g(1)=∑i=0n(−1)n−i(ni)(f(1)+i)n ,令f(1)=pg(1)=∑k=0n(nk)pn−k∑i=0n(−1)n−i(ni)ik=∑k=0n(nk)pn−k∑i=0n(−1)n−i(ni)∑j=0k{kj}j!(ij)=∑k=0n(nk)pn−k∑j=0k{kj}j!∑i=jn(−1)n−i(nj)(n−ji−j)=∑k=0n(nk)pn−k∑j=0k{kj}j!(nj)∑i=0n−j(−1)n−i−j(n−ji)=∑k=0n(nk)pn−k∑j=0k{kj}j!(nj)[n==j]=n!{nn}=n!g(1)=\sum_{i=0}^n(-1)^{n-i}\binom ni(f(1)+i)^n\ ,令f(1)=p\\ g(1)=\sum_{k=0}^n\binom nkp^{n-k} \sum_{i=0}^n(-1)^{n-i}\binom nii^k\\ =\sum_{k=0}^n\binom nk p^{n-k}\sum_{i=0}^n(-1)^{n-i}\binom ni\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\binom ij\\ =\sum_{k=0}^n\binom nk p^{n-k}\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=j}^n(-1)^{n-i}\binom nj\binom {n-j}{i-j}\\ =\sum_{k=0}^n\binom nk p^{n-k}\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\binom nj\sum_{i=0}^{n-j}(-1)^{n-i-j}\binom{n-j}i\\ =\sum_{k=0}^n\binom nk p^{n-k}\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\binom nj[n==j]\\ =n!\begin{Bmatrix}n\\n\end{Bmatrix}=n!

这里的k不是题中的k(推式子不如打表)

接下来就是快速阶乘算法板子(不如分块打表)