题解 | #[NCT058D]大水题#

[NCT058D]大水题

$g(1)={\sum }_{i=0}^n(-1{)}^{n-i}\left(\genfrac{}{}{0px}{}{n}{i}\right)(f(1)+i{)}^n,\mathrm{令}f(1)=pg(1)={\sum }_{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)p^{n-k}{\sum }_{i=0}^n(-1{)}^{n-i}\left(\genfrac{}{}{0px}{}{n}{i}\right)i^k={\sum }_{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)p^{n-k}{\sum }_{i=0}^n(-1{)}^{n-i}\left(\genfrac{}{}{0px}{}{n}{i}\right){\sum }_{j=0}^k\left\{\begin{array}{c}k\\ j\end{array}\right\}j!\left(\genfrac{}{}{0px}{}{i}{j}\right)={\sum }_{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)p^{n-k}{\sum }_{j=0}^k\left\{\begin{array}{c}k\\ j\end{array}\right\}j!{\sum }_{i=j}^n(-1{)}^{n-i}\left(\genfrac{}{}{0px}{}{n}{j}\right)\left(\genfrac{}{}{0px}{}{n-j}{i-j}\right)={\sum }_{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)p^{n-k}{\sum }_{j=0}^k\left\{\begin{array}{c}k\\ j\end{array}\right\}j!\left(\genfrac{}{}{0px}{}{n}{j}\right){\sum }_{i=0}^{n-j}(-1{)}^{n-i-j}\left(\genfrac{}{}{0px}{}{n-j}{i}\right)={\sum }_{k=0}^n\left(\genfrac{}{}{0px}{}{n}{k}\right)p^{n-k}{\sum }_{j=0}^k\left\{\begin{array}{c}k\\ j\end{array}\right\}j!\left(\genfrac{}{}{0px}{}{n}{j}\right)[n==j]=n!\left\{\begin{array}{c}n\\ n\end{array}\right\}=n!g(1)=\backslash sum\_\{i=0\}^n(-1)^\{n-i\}\backslash binom\; ni(f(1)+i)^n\backslash \; ,令f(1)=p\backslash \backslash \; g(1)=\backslash sum\_\{k=0\}^n\backslash binom\; nkp^\{n-k\}\; \backslash sum\_\{i=0\}^n(-1)^\{n-i\}\backslash binom\; nii^k\backslash \backslash \; =\backslash sum\_\{k=0\}^n\backslash binom\; nk\; p^\{n-k\}\backslash sum\_\{i=0\}^n(-1)^\{n-i\}\backslash binom\; ni\backslash sum\_\{j=0\}^k\backslash begin\{Bmatrix\}k\backslash \backslash j\backslash end\{Bmatrix\}j!\backslash binom\; ij\backslash \backslash \; =\backslash sum\_\{k=0\}^n\backslash binom\; nk\; p^\{n-k\}\backslash sum\_\{j=0\}^k\backslash begin\{Bmatrix\}k\backslash \backslash j\backslash end\{Bmatrix\}j!\backslash sum\_\{i=j\}^n(-1)^\{n-i\}\backslash binom\; nj\backslash binom\; \{n-j\}\{i-j\}\backslash \backslash \; =\backslash sum\_\{k=0\}^n\backslash binom\; nk\; p^\{n-k\}\backslash sum\_\{j=0\}^k\backslash begin\{Bmatrix\}k\backslash \backslash j\backslash end\{Bmatrix\}j!\backslash binom\; nj\backslash sum\_\{i=0\}^\{n-j\}(-1)^\{n-i-j\}\backslash binom\{n-j\}i\backslash \backslash \; =\backslash sum\_\{k=0\}^n\backslash binom\; nk\; p^\{n-k\}\backslash sum\_\{j=0\}^k\backslash begin\{Bmatrix\}k\backslash \backslash j\backslash end\{Bmatrix\}j!\backslash binom\; nj[n==j]\backslash \backslash \; =n!\backslash begin\{Bmatrix\}n\backslash \backslash n\backslash end\{Bmatrix\}=n!$

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

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