P5136 sequence

orz_z · 2021-12-24 21:11:01 · 题解

求：

sol

首先考虑将原式转换为：

显然有：

其中 f 为斐波那契数列。

考虑用矩阵快速幂优化递推计算。

显然，设状态矩阵为：

显然，转移矩阵为：

最后再来看看减去的 \left(\frac{1-\sqrt{5}}{2}\right)^{i} 对最终答案的影响。

考虑分奇偶性讨论：

• 当 i 为偶数时，-\left(\frac{1-\sqrt{5}}{2}\right)^{i} 为负，无影响。
• 当 i 为奇数时，-\left(\frac{1-\sqrt{5}}{2}\right)^{i} 为正，最终答案加一。

那就没了。。。

#include <bits/stdc++.h>

using namespace std;

#define int long long

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

int T, n;

const int MOD = 998244353;

struct mat
{
    int a[2][2];
    mat()
    {
        memset(a, 0, sizeof a);
    }
    mat operator*(const mat &b) const
    {
        mat op;
        for (int i = 0; i < 2; i++)
            for (int k = 0; k < 2; k++)
                for (int j = 0; j < 2; j++)
                    op.a[i][j] = (op.a[i][j] + a[i][k] * b.a[k][j]) % MOD;
        return op;
    }
} ans, I;

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

signed main()
{
    T = read();
    while (T--)
    {
        n = read();
        init();
        if (n == 0)
        {
            printf("1\n");
            continue;
        }
        else if (n == 1)
        {
            printf("2\n");
            continue;
        }
        bool flag = 0;
        if(n % 2 == 1) flag = 1;
        n -= 2;
        while (n)
        {
            if (n & 1)
                ans = ans * I;
            I = I * I;
            n >>= 1;
        }
        printf("%lld\n", (ans.a[0][0] + flag) % MOD);
    }
    return 0;
}