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),然后质数我们可以用线性筛法预处理出来

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2014/06/bzoj-3157

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

2 thoughts on “BZOJ-3157. 国王奇遇记

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.