P5136 sequence 题解

Matr1xqwq · 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}。

由于 $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;
}