BZOJ-4002. [JLOI2015]有意义的字符串

给定正整数 b, d, n,计算

 \left \lfloor \left (\frac{b + \sqrt d}{2}\right )^n \right \rfloor \bmod 7528443412579576937

其中 0 < b^2 \leq d < (b + 1)^2 \leq 10^{18}, n \leq 10^{18},并且 b \bmod 2 = 1, d \bmod 4 = 1

题目连接:BZOJ-4002(这里的题面不完全,我上面打出来的是完整的)

这题的样例中 b = 1, d = 5, n = 9,带入之后会发现要求的是  \left (\frac{1 + \sqrt 5}{2}\right )^9

如果对 Fibonacci 数列比较熟悉的话就会发现它正是其通项公式中的一部分

而且,根据特征根法,二阶常系数线性递推数列的通项基本都是长成下面这样子

c_1 (A + \sqrt B)^n + c_2 (A - \sqrt B)^n

然后再看题目要求的式子,可以猜想它是某个这种线性递推数列通项的一部分,如果真的是这样,那么另外一部分就是 \left(\frac{b - \sqrt d}{2}\right)^n, 根据题目中给出的条件可以知道 \frac{b - \sqrt d}{2} \in (-0.5, 0],也就是如果我们找到一个数列 a_n = \left (\frac{b + \sqrt d}{2}\right )^n + \left (\frac{b - \sqrt d}{2}\right )^n 的递推式,就可以利用矩阵快速幂来求出第 n 项,如果 a_n 每一项都是整数,那么答案与 a_n 的误差不会超过 1,现在来求这个数列的递推式

{a_n} 的特征方程是 Ax^2 + Bx + C = 0

根据其通项可以知道

 \begin{eqnarray*}
\left\{
\begin{aligned}
B^2-4AC&=d\\
-B&=b \\
2A&=2
\end{aligned}
\right.
\end{eqnarray*}

最后可以得到 A=1, B = -b, C = \frac{b^2 - d}{4},因此这个数列是

 a_n = ba_{n-1}-\frac{b^2-d}{4}a_{n-2}, a_0 = 2, a_1 = b

再根据题目的条件可以知道 \frac{b^2-d}{4} \in \mathbb Z,这样 a_n \in \mathbb Z,所以刚刚所有的要求都满足了

现在来考虑什么时候会产生误差,因为

 \left (\frac{b + \sqrt d}{2}\right )^n = a_n - \left (\frac{b - \sqrt d}{2}\right )^n

并且 b - \sqrt d < 0,所以当 n 是偶数的时候,答案是 a_n - 1,否则答案是 a_n

吐槽:你萌可以试试看把模数 7528443412579576937 直接解释成字符串输出看看会发生什么(要在 Little-Endian 的 CPU 上才行嗯)

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

miskcoo

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

3 thoughts on “BZOJ-4002. [JLOI2015]有意义的字符串

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.