斐波那契数列卷积

链接：

来源：牛客网

题目描述

已知数列 an=∑k=0nFn−k×Fka_n=\sum_{k=0}^{n}F_{n-k} \times 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的

题解在这

#include 
    
     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\n");    else if(n == 2) printf("1\n");    else if(n == 3) printf("2\n");    else if(n == 4) printf("5\n");    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\n",(ans + mod) % mod);    }    return 0;}