結果

問題 No.1569 Nixoracci's Number
コンテスト
ユーザー flippergo
提出日時 2024-10-13 14:03:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,613 bytes
コンパイル時間 3,665 ms
コンパイル使用メモリ 93,920 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-13 14:03:07
合計ジャッジ時間 4,891 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;

int N, K;
vector<int> A;

vector<vector<int>> matmul(const vector<vector<int>>& X, const vector<vector<int>>& Y) {
    vector<vector<int>> Z(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            for (int k = 0; k < N; ++k) {
                Z[i][j] ^= (X[i][k] * Y[k][j]); // XOR演算
            }
        }
    }
    return Z;
}

vector<vector<int>> matpow(const vector<vector<int>>& X, int k) {
    vector<vector<int>> I(N, vector<int>(N, 0));
    for (int i = 0; i < N; ++i) {
        I[i][i] = 1; // 単位行列の作成
    }

    if (k == 0) return I;
    if (k == 1) return X;

    if (k % 2 == 0) {
        vector<vector<int>> half_pow = matpow(X, k / 2);
        return matmul(half_pow, half_pow);
    } else {
        vector<vector<int>> half_pow = matpow(X, (k - 1) / 2);
        vector<vector<int>> Y = matmul(half_pow, half_pow);
        return matmul(X, Y);
    }
}

int main() {
    cin >> N >> K;
    A.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    int T = N + 1;
    int M = (K - 1) % T;

    vector<vector<int>> A1(N, vector<int>(N, 0));

    // A1行列の初期化
    for (int i = 0; i < N - 1; ++i) {
        A1[i][i + 1] = 1;
    }
    for (int j = 0; j < N; ++j) {
        A1[N - 1][j] = 1;
    }

    // A1をM回累乗した行列を計算
    vector<vector<int>> B = matpow(A1, M);

    // 答えを計算
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        ans ^= (B[0][i] * A[i]);
    }

    cout << ans << endl;

    return 0;
}
0