F

题意

第一部分：给定 ，其中 ，求 。

第二部分：多组询问 ，求 ，其中 是斐波那契数列。

题解

第一部分：矩阵快速幂，记录 这七个值的转移即可。转移矩阵可以通过简单计算得出。

第二部分：利用 即可。

#include <bits/stdc++.h>
#define MOD 998244353
using namespace std;
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
char s[50];
int a1, a2, a3, x, y, z;
__int128_t n;
void init1(){
    scanf("%s%d%d%d%d%d%d", s, &a1, &a2, &a3, &x, &y, &z);
    int l = strlen(s);
    n = 0;
    for (int i = 0; i < l; ++i)
        n = n * 10 + s[i] - '0';
}
int I[7][7] = {0}, A[7][7] = {0}, B[7][7] = {0}, vec[7];
void mul(int F[][7], int G[][7], int H[][7]){
    for (int i = 0; i < 7; ++i){
        for (int j = 0; j < 7; ++j){
            int res = 0;
            for (int k = 0; k < 7; ++k)
                res = modadd(res, 1ll * F[i][k] * G[k][j] % MOD);
            H[i][j] = res;
        }
    }
}
void solve1(){
    if (n == 1) {
        int res = 1ll * a1 * a1 % MOD;
        printf("%d\n", res);
        return ;
    }
    if (n == 2){
        int res = 1ll * a1 * a1 % MOD;
        res = modadd(res, 1ll * a2 * a2 % MOD);
        printf("%d\n", res);
        return ;
    }
    int t1 = modadd(1ll * z * z % MOD, 2ll * x * y % MOD * z % MOD);
    int t2 = modadd(2ll * y * z % MOD, 2ll * x * x % MOD * z % MOD);
    for (int i = 0; i < 7; ++i) I[i][i] = 1;
    A[0][0] = 1ll * x * x % MOD;
    A[0][1] = 1ll * y * y % MOD;
    A[0][2] = t1;
    A[0][3] = 2ll * x * y % MOD;
    A[0][4] = t2;
    A[0][5] = 2ll * x * z % MOD * z % MOD;
    A[3][0] = x;
    A[3][2] = 1ll * y * z % MOD;
    A[3][3] = y;
    A[3][4] = 1ll * x * z % MOD;
    A[3][5] = 1ll * z * z % MOD;
    A[1][0] = A[2][1] = A[4][3] = A[5][4] = A[6][0] = A[6][6] = 1;
    n -= 3;
    while (n > 0){
        if (n % 2 != 0){
            mul(I, A, B);
            for (int i = 0; i < 7; ++i)
                for (int j = 0; j < 7; ++j)
                    I[i][j] = B[i][j];
        }
        mul(A, A, B), n /= 2;
        for (int i = 0; i < 7; ++i)
            for (int j = 0; j < 7; ++j)
                A[i][j] = B[i][j];
    }
    int a4 = modadd(1ll * x * a3 % MOD, modadd(1ll * y * a2 % MOD, 1ll * z * a1 % MOD));
    vec[0] = 1ll * a4 * a4 % MOD;
    vec[1] = 1ll * a3 * a3 % MOD;
    vec[2] = 1ll * a2 * a2 % MOD;
    vec[3] = 1ll * a4 * a3 % MOD;
    vec[4] = 1ll * a3 * a2 % MOD;
    vec[5] = 1ll * a2 * a1 % MOD;
    vec[6] = modadd(1ll * a1 * a1 % MOD, modadd(1ll * a2 * a2 % MOD, 1ll * a3 * a3 % MOD));
    int ans = 0;
    for (int i = 0; i < 7; ++i)
        ans = modadd(ans, 1ll * I[6][i] * vec[i] % MOD);
    printf("%d\n", ans);
}
pair<int, int> fib(int n) {
    if (n == 0) return {0, 1};
    auto p = fib(n >> 1);
    int c = 1ll * p.first * modadd(2ll * p.second % MOD, MOD - p.first) % MOD;
    int d = modadd(1ll * p.first * p.first % MOD, 1ll * p.second * p.second % MOD);
    if (n & 1)
        return {d, modadd(c, d)};
    else
        return {c, d};
}
void solve2(){
    int q, x;
    scanf("%d", &q);
    while (q--){
        scanf("%d", &x);
        auto p = fib(x);
        int ans = 1ll * p.first * p.second % MOD;
        printf("%d\n", ans);
    }
}
int main(){
    init1();
    solve1();
    solve2();
    return 0;
}