Description

给定\(n,k\),求\(\displaystyle \sum _ { i = 1 } ^ { N } \left( \begin{array} { l } { n } \\ { i } \end{array} \right) \times i ^ { k } \bmod \; 10^9 + 7\)
\(n \leq 10^9, k \leq 5 \times 10^3\)

Solution

斯特林变换

因为我们有\( \displaystyle n ^ { k } = \sum _ { i = 1 } ^ { k } \left\{
\begin{array}{c}
k \\
i \\
\end{array}
\right\} \times n ^ { i }\)
于是\(\displaystyle 原式=\sum _ { i = 1 } ^ { n } \sum _ { j = 1 } ^ { k } C _ { n } ^ { i } \times A _ { i } ^ { j } \left\{
\begin{array}{c}
k \\
j \\
\end{array}
\right\} =
\sum _ { j = 1 } ^ { k } \left\{
\begin{array}{c}
k \\
j \\
\end{array}
\right\} \times \sum _ { i = 1 } ^ { n } C _ { n } ^ { i } \times A _ { i } ^ { j }
=
\sum _ { j = 1 } ^ { k } \left\{
\begin{array}{c}
k \\
j \\
\end{array}
\right\} \times A _ { n } ^ { j } \times 2 ^ { n – j }\)
于是我们\( O(k^2) \)弄出斯特林数就ok了


打赏作者
2+

发表评论

电子邮件地址不会被公开。 必填项已用*标注