斐波那契自卷积

牛客挑战赛32 C

不会推导，贴一个oeis链接
https://oeis.org/A001629
通过链接我们知道:

这样我们就可以通过矩阵快速幂求解

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 998244353;
template <typename T>
void out(T x) { cout << x << endl; }
ll fast_pow(ll a, ll b, ll p) {ll c = 1; while(b) { if(b & 1) c = c * a % p; a = a * a % p; b >>= 1;} return c;}
struct Mat
{
    ll p[4][4];
    Mat()
    {
        memset(p, 0, sizeof(p));
    }
    void init()
    {
        for(ll i = 0; i < 4; i ++)
            p[i][i] = 1;
    }
    Mat operator * (const Mat a) const 
    {
        Mat c = Mat();
        for(ll i = 0; i < 4; i ++)
            for(ll j = 0; j < 4; j ++)
                for(ll k = 0; k < 4; k ++)
                    c.p[i][j] = (c.p[i][j] + p[i][k] * a.p[k][j] % mod + mod) % mod;
        return c;
    }
};
Mat fast_pow(Mat a, ll b)
{
    Mat c = Mat();
    c.init();
    while(b)
    {
        if(b & 1)
            c = c * a;
        a = a * a;
        b >>= 1;
    }
    return c;
}
ll a[5] = {0, 0, 1, 2}; 
int main()
{
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    if(n <= 3)
    {
        cout << a[n] << endl;
        return 0;
    }
    Mat a = Mat();
    a.p[0][0] = 2; a.p[0][1] = 1; a.p[0][2] = -2; a.p[0][3] = -1;
    a.p[1][0] = a.p[2][1] = a.p[3][2] = 1;
    a = fast_pow(a, n - 3);
    ll ans = (2 * a.p[0][0] % mod + a.p[0][1] + mod) % mod;
    cout << ans << endl;
}