斐波那契数列卷积(矩阵快速幂）

斐波那契数列卷积

链接：

https://ac.nowcoder.com/acm/contest/1087/C

来源：牛客网

题目描述

已知数列 an=∑k=0nFn−k×Fka_n=sum_{k=0}^{n}F_{n-k} imes F_kan=∑k=0nFn−k×Fk ，其中 F 是斐波那契数列，递推式为：
F0=0,F1=1F_0=0,F_1=1F0​=0,F1​=1，满足Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}Fn​=Fn−1​+Fn−2​，需要求出ana_nan​mod 998244353

输入描述:

一行一个整数 n


对于 100% 的数据，满足 1≤n≤10181 leq n leq 10^{18}1≤n≤1018

输出描述:

一行一个整数表示答案

示例1

输入

3

输出

2

示例2

输入

19260817

输出

511682927

题解：久违的ac，虽然是看题解a的

题解在这https://ac.nowcoder.com/acm/problem/blogs/52937

#include <cstdio>
typedef long long LL;
const LL mod = 998244353;
struct node
{
    LL v[5][5];
};
//矩阵相乘
node get_mul(node a, node b) {
    node c;
    for(int i = 0; i < 4; i++) {
        for(int j = 0; j < 4; j++) {
            c.v[i][j] = 0;
            for(int k = 0; k < 4; k++) {
                c.v[i][j] = (c.v[i][j] % mod + a.v[i][k] % mod * b.v[k][j] % mod) % mod;
            }
        }
    }
    return c;
}

int main() {
    LL n;
    scanf("%lld", &n);
    if(n == 1) printf("0
");
    else if(n == 2) printf("1
");
    else if(n == 3) printf("2
");
    else if(n == 4) printf("5
");
    else {
        LL d[5];
        d[0] = 5, d[1] = 2, d[2] = 1;
        node a, b;
        a.v[0][0] = 2, a.v[0][1] = 1, a.v[0][2] = 0, a.v[0][3] = 0;
        a.v[1][0] = 1, a.v[1][1] = 0, a.v[1][2] = 1, a.v[1][3] = 0;
        a.v[2][0] =-2, a.v[2][1] = 0, a.v[2][2] = 0, a.v[2][3] = 1;
        a.v[3][0] =-1, a.v[3][1] = 0, a.v[3][2] = 0, a.v[3][3] = 0;
        \矩阵b=1
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                b.v[i][j] = 0;
            }
            b.v[i][i] = 1;
        }
        n -= 4;
        while(n) {
            if(n&1) b = get_mul(a, b);
            a = get_mul(a, a);
            n >>= 1;
        }
        LL ans = 0;
        for(int i = 0; i < 3; i++) ans = (ans % mod + b.v[i][0] * d[i] % mod) % mod;
        printf("%lld
",(ans + mod) % mod);
    }
    return 0;
}