bzoj4002 [JLOI2015]有意义的字符串特征根+矩阵快速幂

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=4002

题解

神仙题。

根据下面的一个提示：

\[b^2 \leq d \leq (b+1)^2
\]

也就是说 \(-1 < b - \sqrt d \leq 0\)。

那么如果我们构造出一个数列 \(f\)，其通项公式为

\[f_n = (\frac{b + \sqrt d}{2})^n + (\frac{b - \sqrt d}{2})^n
\]

因为后面的 \((\frac{b - \sqrt d}{2})^n\) 的绝对值 \(< 1\)，（在 \(2 | n\) 且 \(b \neq \sqrt d\) 的时候 \(> 0\)，否则 \(<0\)）。所以我们只要能求出这个东西，就可以非常快速地求出原题的要求的式子了。

发现这个东西非常像由特征根构造的通项公式。于是我们设 \(f_n = a \cdot f_{n-1} + c \cdot f_{n-2}\)。

\[x^2=ax+c\\x^2-ax-c=0\\x = \frac{a\pm \sqrt{a^2 + 4c}}{2}
\]

于是令 \(a = b, c = \frac{d - b^2}4\)。

正确性很容易验证。

然后用矩阵求一下即可。

在 \(2 | n\) 且 \(b \neq \sqrt d\) 的时候需要把 \(a_n - 1\)。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

const ull P = 7528443412579576937;

ull n, b;

ull d;

inline ull smod(ull x) { return x >= P ? x - P : x; }

inline void sadd(ull &x, const ull &y) { x += y; x >= P ? x -= P : x; }

inline ull fmul(ull x, ull y) {

	ull ans = 0;

	for (; y; y >>= 1, sadd(x, x)) if (y & 1) sadd(ans, x);

	return ans;

}

struct Matrix {

	ull a[2][2];

	inline Matrix() { memset(a, 0, sizeof(a)); }

	inline Matrix(const ull &x) {

		memset(a, 0, sizeof(a));

		a[0][0] = a[1][1] = x;

	}

	inline Matrix operator * (const Matrix &b) {

		Matrix c;

		c.a[0][0] = smod(fmul(a[0][0], b.a[0][0]) + fmul(a[0][1], b.a[1][0]));

		c.a[0][1] = smod(fmul(a[0][0], b.a[0][1]) + fmul(a[0][1], b.a[1][1]));

		c.a[1][0] = smod(fmul(a[1][0], b.a[0][0]) + fmul(a[1][1], b.a[1][0]));

		c.a[1][1] = smod(fmul(a[1][0], b.a[0][1]) + fmul(a[1][1], b.a[1][1]));

		return c;

	}

} A, B;

inline Matrix fpow(Matrix x, ull y) {

	Matrix ans(1);

	for (; y; y >>= 1, x = x * x) if (y & 1) ans = ans * x;

	return ans;

}

inline void work() {

	if (n == 0) return (void)puts("1");

	B.a[0][0] = b, B.a[1][0] = 2;

	A.a[0][0] = b, A.a[0][1] = (d - (ull)b * b) / 4;

	A.a[1][0] = 1, A.a[1][1] = 0;

	B = fpow(A, n - 1) * B;

	if (n & 1) printf("%llu\n", B.a[0][0]);

	else printf("%llu\n", B.a[0][0] - !((ull)b * b == d));

}

inline void init() {

	read(b), read(d), read(n);

}

int main() {

#ifdef hzhkk

	freopen("hkk.in", "r", stdin);

#endif

	init();

	work();

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

bzoj4002 [JLOI2015]有意义的字符串特征根+矩阵快速幂

题目传送门

题解

最新文章

热门文章

巴特西

bzoj4002 [JLOI2015]有意义的字符串 特征根+矩阵快速幂

题目传送门

题解

最新文章

热门文章

bzoj4002 [JLOI2015]有意义的字符串特征根+矩阵快速幂