自动搬运

查看原文

来自洛谷，原作者为

	Transfixion_ AFOed

搬运于2025-08-24 22:07:30，当前版本为作者最后更新于2022-03-18 18:25:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目链接：$\texttt{Link}$

$\textbf{Update}$

• 2022.10.24 被 @lingfunny Hack 了。

• 2023.3.1 修改并重写题解 & 代码。

$\textbf{Description}$

已知 $1\le n\le 10^{18}$，试求出

$$\left\lceil{\left(\dfrac{\sqrt 5 + 1}{2} \right)}^n\right\rceil $$

$\textbf{Solution}$

显然这是一个斐波那契数列。

考虑其共轭：设 $ x = \dfrac{\sqrt 5 + 1}{2}, y = \dfrac{1 - \sqrt 5}{2}$。

由共轭的性质，$x+y=1,xy=-1$。

那么一个思路是构造数列 $F_n = x^n + y^n$。

$\begin{aligned}F_n&=(x+y)(x^{n-1}+y^{n-1})-xy(x^{n-2}+y^{n-2})\\&=(x+y)F_{n-1}-xy\times F_{n-2}\\&=F_{n-1}+F_{n-2}.\end{aligned}$

也就是 $F_n=F_{n-1}+F_{n-2}$，即证。

我们需要通过 $\begin{bmatrix}F_{n-1} & F_{n-2}\end{bmatrix}$ 推得 $\begin{bmatrix}F_{n} & F_{n-1}\end{bmatrix}$。

手推一下得到 $\begin{bmatrix}F_{n-1} & F_{n-2}\end{bmatrix} \times \begin{bmatrix}1&1\\1&0\end{bmatrix} = \begin{bmatrix}F_{n} & F_{n-1}\end{bmatrix}$。

$F_n$ 的问题已经解决，考虑 $A_n$。

由于 $A_n=\lceil F_n-y^n\rceil$，我们需要讨论 $y^n$ 的范围。

注意到 $y \in (-1, 0)$，于是：

• $n$ 为奇数时，$y^n\in(-1,0)\Rightarrow A_n = F_n+1$；

• $n$ 为偶数时，$y^n\in(0,1)\Rightarrow A_n = F_n$。

$\textbf{Extra}$

• 注意取模 & 溢出问题；
• 特判 $n=0$ 和 $n=1$ 的情况；
• 注意 $F_1=1,F_2=3$。

$\textbf{AC Code}$

#include <bits/stdc++.h>
#define int long long
const int p = 998244353;
int T, n;

struct Matrix {
    int a[2][2];
    Matrix() {memset(a, 0, sizeof(a));}
    Matrix operator * (const Matrix &mat) {
	    Matrix res;
	    for(int i = 0; i < 2; i++) {
		    for(int k = 0; k < 2; k++) {
				for(int j = 0; j < 2; j++) {
				    res.a[i][j] += a[i][k] * mat.a[k][j];
				    res.a[i][j] %= p;
				}
			}
		} return res;
	}
}ans, base;

inline void init() {
	base.a[0][0] = 1, base.a[0][1] = 1;
	base.a[1][0] = 1, base.a[1][1] = 0;
	ans.a[0][0] = 3, ans.a[0][1] = 1;
	ans.a[1][0] = 0, ans.a[1][1] = 0;
}

inline int solve(int b) {
	init();
	int f = (b -= 2) & 1;
	while(b) {
		if(b & 1) ans = ans * base;
		base = base * base, b >>= 1;
	} return (ans.a[0][0] + f) % p;
	// Hack:注意先加再取模
}

signed main() {
	std::cin >> T;
	while(T--) {
		std::cin >> n;
		if(n == 0) {puts("1"); continue;}
		if(n == 1) {puts("2"); continue;}
		std::cout << solve(n) << std::endl;
	}
    return 0;
}