原题链接
题解
题目等价于求这个式子
\[ans=n2^{\frac{(n-1)(n-2)}{2}}\sum\limits_{i=0}^{n-1}\binom{n-1}{i}i^k
\]
有这么一个式子
\[i^k=\sum\limits_{j=0}^{i}\begin{Bmatrix}
k\\
j
\end{Bmatrix}j!\binom{i}{j}\]
代入可得
\[ans=n2^{\frac{(n-1)(n-2)}{2}}\sum\limits_{i=0}^{n-1}\binom{n-1}{i}\sum\limits_{j=0}^{i}\begin{Bmatrix}
k\\
j
\end{Bmatrix}j!\binom{i}{j}\]
交换枚举顺序
\[ans=n2^{\frac{(n-1)(n-2)}{2}}\sum\limits_{j=0}^{n-1}\begin{Bmatrix}
k\\
j
\end{Bmatrix}j!\sum\limits_{i=j}^{n-1}\binom{n-1}{i}\binom{i}{j}\]
考虑到后面那个和号的组合意义为先在\(n-1\)个数中确定\(j\)个，剩下的可选可不选，即
\[ans=n2^{\frac{(n-1)(n-2)}{2}}\sum\limits_{j=0}^{n-1}\begin{Bmatrix}
k\\
j
\end{Bmatrix}j!\binom{n-1}{j}2^{n-1-j}
\]
\[=n2^{\frac{(n-1)(n-2)}{2}}\sum\limits_{j=0}^{n-1}\begin{Bmatrix}
k\\
j
\end{Bmatrix}\frac{(n-1)!}{(n-1-j)!}2^{n-1-j}\]
本题的\(n\)可能高达\(10^9\)，但是发现当\(j>k\)时\(\begin{Bmatrix}
k\\
j
\end{Bmatrix}\)为\(0\)，改一下求和上界
\[=n2^{\frac{(n-1)(n-2)}{2}}\sum\limits_{j=0}^{min\{n-1,k\}}\begin{Bmatrix}
k\\
j
\end{Bmatrix}\frac{(n-1)!}{(n-1-j)!}2^{n-1-j}\]
第二类斯特林数可以直接卷积出来，总复杂度\(O(nlogn)\)
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include