「JLOI2015」有意义的字符串

发表于
https://loj.ac/problem/2106

题目链接

「JLOI2015」有意义的字符串

做法

$ \frac{b + \sqrt{d}}{2} $ 和 $ \frac{b - \sqrt{d}}{2} $ 是二元一次方程 $ x^2 - bx + \frac{b^2 - d}{4} = 0 $ 的解。
则 $ x^2 = bx + \frac{d - b^2}{4} $ 。
两边同时乘 $ x^{n - 2} $ 得： $ x^n = bx^{n - 1} + \frac{d - b^2}{4}x^{n - 2} $ 。
设 $ f[i] = (\frac{b + \sqrt{d}}{2})^{i} + (\frac{b - \sqrt{d}}{2})^{i} $ ，则存在递推式 $ f[i] = bf[i - 1] + \frac{d - b^2}{4}f[i - 2] $ 。其中 $ f[0] = 2, f[1] = b $ 。
这样就矩阵乘法得到 $ f[n] $ 。题目中有 $ b^2 \leq d < (b + 1)^2 $ ，所以 $ \frac{b - \sqrt{d}}{2} \leq 0 $ 。特判 $ b^2 \neq d $ 且 $ n \mod 2 = 0 $ 来判断是否减一。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll mod = 7528443412579576937ll;
ll b, d, n;

inline ll add(const ll &x, const ll &y) {
	return (ull)x + (ull)y < (ull)mod ? (ull)x + (ull)y : (ull)x + (ull)y - (ull)mod; }
inline ll sub(const ll &x, const ll &y) {
	return (ull)x - (ull)y < (ull)0 ? (ull)x - (ull)y + (ull)mod : (ull)x - (ull)y;
}
inline ll mul(ll x, ll y) {
	ll ss = 0; for(; y; y /= 2, x = add(x, x)) if(y % 2) ss = add(ss, x);
	return ss;
}
struct mtrx {
	ll a[2][2]; mtrx() { memset(a, 0, sizeof(a)); }
	inline mtrx operator*(const mtrx &yy)const {
		mtrx res;
		for(int i = 0; i < 2; i++)
			for(int j = 0; j < 2; j++)
				for(int k = 0; k < 2; k++)
					res.a[i][j] = add(res.a[i][j], mul(a[i][k], yy.a[k][j]));
		return res;
	}
}; mtrx sum, ba;

ll ksm(ll x, ll y = mod - 2) {
	ll ss = 1; for(; y; y /= 2, x = mul(x, x)) if(y % 2) ss = mul(ss, x);
	return ss;
}
int main() {
	scanf("%lld%lld%lld", &b, &d, &n); ll flag = (n % 2 == 0 && b * b != d);
	if(n == 0) { printf("1\n"); return 0; }
	if(n == 1) { printf("%lld\n", b + (ll)sqrt(d)); return 0; }
	sum.a[0][0] = b, sum.a[1][0] = 2;
	ba.a[0][0] = b, ba.a[0][1] = (d - b * b) / 4, ba.a[1][0] = 1;
	n -= 1; if(n < 0) n = 0; mtrx tmp; tmp.a[0][0] = tmp.a[1][1] = 1;
	for(; n; n /= 2, ba = ba * ba) if(n % 2) tmp = tmp * ba;
	sum = tmp * sum;
	printf("%lld\n", sub(sum.a[0][0], flag));
	return 0;
}