LOJ2106 [JLOI2015]有意义的字符串

经典矩阵乘法计算无理数幂题目。

题意：求

$$\lfloor (\dfrac{b + \sqrt d}2) ^ n \rfloor \bmod 7528443412579576937$$

$b ^ 2\leq d < (b + 1) ^ 2\leq 10 ^ {18}$，$b\bmod 2 = 1$，$d\bmod 4 = 1$。

首先样例给出了一个 $\dfrac{1 + \sqrt 5}{2}$（这个怎么不符合数据范围啊）的例子，我们很容易联想到计算 $(\dfrac {1 + \sqrt 5} 2) ^ n + (\dfrac {1 - \sqrt 5} 2) ^ n$，因为这是斐波那契数列的通项公式。

同样的，我们可以考虑计算 $(\dfrac{b + \sqrt d}2) ^ n + (\dfrac {b - \sqrt d}{2}) ^ n$ 的答案。容易发现这两个无理数其实是 $x ^ 2 - bx + \dfrac{b ^ 2 - d}{4} = 0$ 的两根。

然后给出一个经典结论：

马上可以得到递推式为 $f_n = bf_{n - 1} + \dfrac{d - b ^ 2}4 f_{n - 2}$。

证明可以考虑展开该式子。

设 $a_1 = \dfrac{b + \sqrt d}2$，$a_2 = \dfrac{b - \sqrt d}2$，那么我们的答案就是 $a_1 ^ n + a_2 ^ n$。考虑化出 $a_1 ^ {n - 1} + a_2 ^ {n - 1}$，那么容易发现需要乘上一个 $a_1 + a_2$，但是还是会多一些项，我们整理一下，可以得到：

$$a_1 ^ n - a_2 ^ n = (a_1 + a_2) (a_1 ^ {n - 1} + a_2 ^ {n - 1}) - a_1a_2(a_1 ^ {n - 2} + a_2 ^ {n - 2})$$

于是代换为 $f_n$ 就可以得到上面的式子。至于为什么要扯到一元二次方程，是因为其实这个就是韦达定理（

这样剩下的，我们只需要求出 $f_0, f_1$ 即可用矩阵乘法得到 $f_n$。

但是原问题还没完：怎么求得下取整的答案？

容易发现由于题目限制，我们很容易得到 $b - \sqrt d \in(-1, 0]$，那么显然 $(\dfrac{b - \sqrt d}2) ^ n$ 的绝对值 $<1$。如果 $n$ 是偶数，并且 $b\not = \sqrt d$，那么加了一部分才得到 $f_n$，所以答案应 -1，否则不变。

注意模数很大，需要用龟速乘或者 __int128 计算乘法。

int main()
{
	LL b, d, n;
	std::cin >> b >> d >> n;
	if (n == 0) return puts("1"), 0;
	Matrix st;
	st[1][0] = 1, st[1][1] = b, st[0][1] = (d - b * b) / 4;
	st = qpow(st, n);
	LL res = ((s128) st[1][0] * b + (s128) 2 * st[0][0]) % Mod;
	if (!(n & 1) && d != b * b) res --;
	std::cout << res << '\n';
	return 0;
}