BZOJ-3157. 国王奇遇记

题目大意是要求下面这个式子

$$\begin{eqnarray*} \sum_{i=1}^n m^i \cdot i^m \end{eqnarray*}$$

这个题目有三个版本：

BZOJ-3157 $m \leq 200$

BZOJ-3516 $m \leq 1000$

BZOJ-4126 $m \leq 500000$

这篇文章介绍 $\mathcal O(m^2)$ 和 $\mathcal O(m)$ 两种做法

为了方便，定义一个函数 $f(i)$

$$\begin{eqnarray*} f(i) = \sum_{k=1}^n k^i \cdot m^k \end{eqnarray*}$$

然后使用“扰动法“

$$\begin{eqnarray*} (m - 1) \cdot f(i) & = & \sum_{k=1}^n k^i \cdot m^{k + 1} - \sum_{k=1}^n k^i \cdot m^k \\ & = & \sum_{k=1}^{n + 1} (k - 1)^i \cdot m^k - \sum_{k=1}^n k^i \cdot m^k \\ & = & n^i \cdot m^{n + 1} + \sum_{k=1}^n m^k \sum_{j = 0}^{i - 1} {i \choose j} \cdot (-1)^{i - j} \cdot k^j \\ & = & n^i \cdot m^{n + 1} + \sum_{j = 0}^{i - 1} {i \choose j} \cdot (-1)^{i - j} \sum_{k = 1}^n k^j \cdot m^k \\ & = & n^i \cdot m^{n + 1} + \sum_{j = 0}^{i - 1} {i \choose j} \cdot (-1)^{i - j} \cdot f(j) \\ \end{eqnarray*}$$

然后这个算法的复杂度是 $\mathcal O(m^2)$ 的，但是这题最快可以做到 $\mathcal O(m)$ 的！

我们现在记题目要求的和式为 $F_m(n)$，首先我们可以把 $m$ 比较小的时候的通项列出来试试看，

$$\begin{eqnarray*} F_1(n) &=& \frac{1}{2}1^n(n^2+n) \\ F_2(n) &=& 2^n(2n^2-4n+6) - 6 \\ F_3(n) &=& \frac{3}{8}\left [ 3^n(4n^3-6n^2+12n-11) + 11 \right ] \\ F_4(n) &=& \frac{4}{81}\left [ 4^n(27n^4-36n^3+90n^2-132n+95) - 95 \right ] \end{eqnarray*}$$

我们发现当 $m > 1$ 的时候 $F_m(n)$ 一定有这样的形式：

$$F_m(n) = m^n P_m(n) - P_m(0)$$

其中 $P_m(n)$ 是一个 $m$ 次多项式，于是只要求出 $P_m(0), P_m(1), \cdots, P_m(n)$ 就可以用这篇文章的方法在 $\mathcal O(m)$ 的时间内计算出 $P_m(n)$ 了！

计算 $F_m(n + 1) - F_m(n)$ 可以得到 $P_m$ 的递推式

$$\begin{eqnarray*} m^{n+1}(n+1)^m &=& m^{n+1}P_m(n+1) - m^nP_m(n) \\ P_m(n+1) &=& \frac{P_m(n)}{m} + (n+1)^m \end{eqnarray*}$$

然后现在我们可以将 $P_m(1), P_m(2), \cdots, P_m(m + 1)$ 都表示成 $A\cdot P_m(0) + B$，一共得到 $m + 1$ 个方程，为了得到 $P_m(0)$ 还缺少一个方程？

我们利用上面所说的那篇文章最后的结论

$$P_m(x) = \sum_{j=0}^m (-1)^{m - j}{x \choose j}{{x - j - 1} \choose {m - j}} P_m(j)$$

当 $x > m$ 的时候这是成立的没有问题，于是，我们令 $x = m + 1$ 可以得到

$$\begin{eqnarray*} P_m(m + 1) &=& \sum_{j=0}^m (-1)^{m - j}{{m + 1} \choose j}{{m - j} \choose {m - j}} P_m(j) \\ 0 &=& \sum_{j=0}^{m+1} (-1)^{m - j}{{m + 1} \choose j} P_m(j)\\ \end{eqnarray*}$$

这就是我们需要的第 $n + 2$ 个方程！然后就可以解出来 $P_m(0)$ 了！然后剩下的就是根据上面文章的方法计算出答案

一些小细节我在这里说一下，因为你是需要计算 $k^n$，这一部分实际上是可以线性时间内预处理的，大概做法是这样，对于每个数，如果是质数，那么我们用快速幂 $\mathcal O(\log n)$ 计算，如果不是质数，那么找出它的一个质因子，然后拆成两份已经计算过的比它小的数相乘可以 $\mathcal O(1)$ 计算，由于质数个数是 $\mathcal O(\frac{n}{\ln n})$ 级别的，因此总复杂度是 $\mathcal O(m)$，然后质数我们可以用线性筛法预处理出来