毒瘤卡常题

题目给我们 $n$，要让我们求 $\lceil(\dfrac{1+\sqrt{5}}{2})\rceil^n \bmod 998244353$。

方法 1

过程

有没有见过斐波那契数列的通项公式？我们设一个序列 $F$，满足：

$$F_n=(\dfrac{1+\sqrt{5}}{2})^n+(\dfrac{1-\sqrt{5}}{2})^{n} $$

现在我们只需要知道 $(\dfrac{1-\sqrt{5}}{2})^n$ 的范围就好了。

然后我们发现 $\dfrac{1-\sqrt{5}}{2}\in(-1,0)$。于是：

• 当 $n\bmod 2=1$ 时， $(\dfrac{1-\sqrt{5}}{2})^n<0$。
• 否则，$(\dfrac{1-\sqrt{5}}{2})^n>0$。

计算 $F_n$

我们设 $x=\dfrac{1+\sqrt{5}}{2},y=\dfrac{1-\sqrt{5}}{2}$。

复习完立方和公式的证明方法之后，我们试着递推：

$$\begin{aligned} F_n&=x^n+y^n\\ &=x^n+y^n+xy^{n-1}+yx^{n-1}-(xy^{n-1}+yx^{n-1})\\ &=(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}\\ \end{aligned} $$

于是转移矩阵为

$$\left[\begin{array}{cc}F_n&F_{n-1}\end{array}\right] \times \left[\begin{array}{cc}F_{n-1}&F_{n-2}\end{array}\right]^{-1}= \left[\begin{array}{cc} 1&1\\ 1&0\\ \end{array}\right] $$

于是就可以递推了。注意 $F_1=1,F_2=3$。

实现

mat base, res;
constexpr mint one(1), zero(0), three(3);
mint ans;
unsigned long long n = 0;
size_t T = 0;
inline void solve() {
    cin >> n;
    if (n == 0) cout << '1' << '\n';
    else if (n == 1) cout << '2' << '\n';
    else {
        base.mat[1][1] = zero;
        base.mat[0][0] = base.mat[0][1] = base.mat[1][0] = one;
        ans = (n & 1);
        n -= 2;
        res.mat[0][0] = three;
        res.mat[1][0] = res.mat[1][1] = zero;
        res.mat[0][1] = one;
        for (; n; base *= base, n >>= 1) if (n & 1) res *= base;
        ans += res.mat[0][0];
        cout << ans << '\n';
    }
}
int main() {
    base.mat.resize(2);
    base.mat[0].resize(2);
    base.mat[1].resize(2);
    res.mat.resize(2);
    res.mat[0].resize(2);
    res.mat[1].resize(2);
    cin >> T;
    for (size_t t = 0; t < T; t++) solve();
}

方法2

求出第 $n$ 个斐波那契数并乘以 $\sqrt{5}$，即得 $\sqrt{5}\times F_n$。

移项，得到 $\sqrt{5}\times F_n+(\dfrac{1-\sqrt{5}}{2})^n=(\dfrac{1+\sqrt{5}}{2})^n$。

按照上述方法，我们分析 $(\dfrac{1-\sqrt{5}}{2})^n$ 的结束了。