bzoj5118 Fib数列2 二次剩余+矩阵快速幂

题目传送门

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

题解

这个题一看就是不可做的样子。

求斐波那契数列的第 \(n\) 项，\(n \leq 2^{10^{15}}\)？？？

这样人怎么矩阵快速幂啊。

等等这个模数很神奇啊。

\(1125899839733759\) 好像是一个质数，还以 \(9\) 结尾。

那么 \(5\) 对于 \(1125899839733759\) 一定有二次剩余咯。

那么根据 Fib 的通项公式

\[f(n) = (\frac{\sqrt 5+1}{2})^n + (\frac{\sqrt 5 - 1}2)^n
\]

那么这个 \(2^n\) 就可以根据费马小定理就可以转化成 \(n \bmod P-1\) 了。

那么这个 \(2^n\) 的范围瞬间小了很多。

于是就可以直接矩阵快速幂了，注意乘法要用快速乘实现。

UPD: 发现好像傻掉了，都有通项公式了，还写什么矩阵快速幂。

时间复杂度 \(O(T\log^2 n)\)。

#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 ll P = 1125899839733759;

ll n;

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

inline ll smod(const ll &x, const ll &P = ::P) { return x >= P ? x - P : x; }

inline ll fmul(ll x, ll y, const ll &P = ::P) {

	ll ans = 0;

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

	return ans;

}

inline ll fpow(ll x, ll y, const ll &P = ::P) {

	ll ans = 1;

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

	return ans;

}

struct Matrix {

	ll 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, ll y) {

	Matrix ans(1);

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

	return ans;

}

inline void work() {

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

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

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

	A = fpow(A, n) * B;

	printf("%lld\n", A.a[0][0]);

}

inline void init() {

	read(n);

	n = fpow(2, n, P - 1);

}

int main() {

#ifdef hzhkk

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

#endif

	int T;

	read(T);

	while (T--) {

		init();

		work();

	}

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

bzoj5118 Fib数列2 二次剩余+矩阵快速幂

题目传送门

题解

最新文章

热门文章