結果

問題 No.3243 Multiplication 8 1
コンテスト
ユーザー ripity
提出日時 2025-08-22 21:36:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 135 ms / 2,000 ms
コード長 1,394 bytes
コンパイル時間 5,618 ms
コンパイル使用メモリ 335,360 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-22 21:36:27
合計ジャッジ時間 6,545 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;

using ll = long long;
using mint = modint998244353;

using MAT = vector<vector<mint>>;

MAT matprod(MAT A, MAT B) {
    int H = A.size();
    int W = B[0].size();
    int K = A[0].size();
    MAT C(H, vector<mint>(W));
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            for(int k = 0; k < K; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

MAT matpow(MAT A, ll n) {
    int N = A.size();
    MAT C(N, vector<mint>(N));
    for(int i = 0; i < N; i++) C[i][i] = 1;
    while(n) {
        if(n & 1) C = matprod(C, A);
        A = matprod(A, A);
        n /= 2;
    }
    return C;
}

void solve() {
    MAT coef = {
        {1, 0, 1, 1, 0, 1, 1},
        {1, 1, 0, 1, 1, 0, 0},
        {0, 1, 1, 0, 1, 1, 0},
        {1, 0, 0, 1, 0, 0, 0},
        {1, 1, 0, 1, 1, 0, 0},
        {0, 1, 1, 0, 1, 1, 0},
        {0, 0, 1, 0, 0, 1, 1}
    };
    MAT fi = {
        {1},
        {0},
        {0},
        {0},
        {0},
        {0},
        {0}
    };
    ll n;
    cin >> n;
    MAT dp = matprod(matpow(coef, n), fi);
    // for(int i = 0; i < 7; i++) cout << dp[i][0].val() << " \n"[i == 6];
    cout << (dp[0][0] - mint(2).pow(n - 1)).val() << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
}
0