[题解]bzoj4002(JLOI2015)有意义的字符串

Description

B 君有两个好朋友，他们叫宁宁和冉冉。有一天，冉冉遇到了一个有趣的题目：输入 b;d;n，求

Input

一行三个整数 b;d;n

Output

一行一个数表示模 7528443412579576937 之后的结果。

Sample Input

1 5 9

Sample Output

76

HINT

其中 0<b2<=d<(b+1)2<=1018,n<=1018$0<b^2< = d<(b+1)^2< = 10^{18},n< = 10^{18}$，并且 b mod 2=1,d mod 4=1

Solution

看看题目中的式子，想想初中数学，是不是很熟悉啊？ 没错，他很像是一元二次方程的根。再联想一下n次方，于是神奇的发现他又像是某数列通项公式中的那个东东。 式子中可以看出，如果一元二次方程x2=px+q$x^2=px+q$的一个根为 (b+d√2)n$(/frac{b+/sqrt{d}}{2})^n$，那么Δ=p2+4q=d$/Delta=p^2+4q=d$，p=−b$p=-b$，所以根据通项公式可以构造出序列： an=b∗an−1+(d−b2)4∗an−2 $$a_n=b*a_{n-1}+/frac{(d-b^2)}{4}*a_{n-2}$$ 他的通项公式为 an=A(b+d‾‾√2)n+B(b−d‾‾√2)n $$a_n=A(/frac{b+/sqrt{d}}{2})^n+B(/frac{b-/sqrt{d}}{2})^n$$ 为了方便计算，我们取A=B=1$A=B=1$，所以 a0=2 $$a_0=2$$ a1=b $$a_1=b$$ 而序列a的递推式中(d−b2)4$/frac{(d-b^2)}{4}$，由于b mod 2=1，d mod 4=1，所以(d−b2)4$/frac{(d-b^2)}{4}$一定是整数，所以矩阵乘法直接求出第n项，所以我们要的答案就是 (b+d‾‾√2)n=an−(b−d‾‾√2)n $$(/frac{b+/sqrt{d}}{2})^n=a_n-(/frac{b-/sqrt{d}}{2})^n$$ 由于题目中给出 b2<=d<(b+1)2$b^2< = d<(b+1)^2$，所以b−d√2∈(−1,0]$/frac{b-/sqrt{d}}{2}/in (-1,0]$，当且仅当b2≠d$b^2/neq d$且n为偶数时对答案有-1的贡献，所以答案要视情况减一。

注意模数太大，所以要开unsigned long long，并且要用快速乘取模。

代码：