結果

問題 No.1569 Nixoracci's Number
コンテスト
ユーザー ooaiu
提出日時 2025-08-26 11:25:56
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 731 ms / 2,000 ms
コード長 3,636 bytes
コンパイル時間 2,990 ms
コンパイル使用メモリ 286,516 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-26 11:26:06
合計ジャッジ時間 8,852 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::static_modint<2>;
using namespace std;
template <class T>
struct Matrix : public std::vector<std::vector<T>> {
    Matrix() = default;
    Matrix(int h, int w, const T& v) : std::vector<std::vector<T>>(h, std::vector<T>(w, v)) {}
    Matrix(int h, int w) : Matrix(h, w, T{}) {}
    Matrix(const std::vector<std::vector<T>>& V) : std::vector<std::vector<T>>(V) {}
    Matrix(std::vector<std::vector<T>>&& V) : std::vector<std::vector<T>>(std::move(V)) {}
    static Matrix eye(int sz) {
        Matrix res(sz, sz);
        for (int i = 0; i < sz; i++) res[i][i] = 1;
        return res;
    }
    int height() const { return this->size(); }
    int width() const { return this->size() ? (*this)[0].size() : 0; }
    bool is_square() const { return height() == width(); }
    Matrix& operator+=(const Matrix& other) {
        assert(height() == other.height() && width() == other.width());
        for (int i = 0; i < height(); i++)
            for (int j = 0; j < width(); j++) {
                (*this)[i][j] += other[i][j];
            }
        return *this;
    }
    Matrix& operator-=(const Matrix& other) {
        assert(height() == other.height() && width() == other.width());
        for (int i = 0; i < height(); i++)
            for (int j = 0; j < width(); j++) {
                (*this)[i][j] -= other[i][j];
            }
        return *this;
    }
    Matrix& operator*=(const Matrix& other) {
        assert(width() == other.height());
        Matrix res(height(), other.width());
        for (int i = 0; i < height(); i++) {
            for (int k = 0; k < width(); k++) {
                for (int j = 0; j < other.width(); j++) {
                    res[i][j] += (*this)[i][k] * other[k][j];
                }
            }
        }
        return *this = std::move(res);
    }
    Matrix& operator*=(T s) {
        for (int i = 0; i < height(); i++) {
            for (int j = 0; j < width(); j++) {
                (*this)[i][j] *= s;
            }
        }
        return *this;
    }
    friend Matrix operator+(const Matrix& lhs, const Matrix& rhs) { return Matrix(lhs) += rhs; }
    friend Matrix operator-(const Matrix& lhs, const Matrix& rhs) { return Matrix(lhs) -= rhs; }
    friend Matrix operator*(const Matrix& lhs, const Matrix& rhs) { return Matrix(lhs) *= rhs; }
    friend Matrix operator*(const Matrix& lhs, T rhs) { return Matrix(lhs) *= rhs; }
    friend Matrix operator*(int lhs, const Matrix& rhs) { return Matrix(rhs) *= lhs; }
    Matrix pow(long long b) const {
        Matrix a = *this, res = eye(height());
        while (b) {
            if (b & 1) res *= a;
            a *= a;
            b >>= 1;
        }
        return res;
    }
    Matrix transpose() const {
        Matrix res(width(), height());
        for (int i = 0; i < height(); i++) {
            for (int j = 0; j < width(); j++) {
                res[j][i] = (*this)[i][j];
            }
        }
        return res;
    }
};
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::fixed(std::cout).precision(16);
    long long N, K;
    cin >> N >> K;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    if (K <= N) cout << (A[K - 1]) << "\n";
    else {
        long long ans = 0;
        Matrix<mint> a(N, N);
        for (int j = 0; j < N; j++) a[0][j] = 1;
        for (int j = 0; j < N - 1; j++) a[j + 1][j] = 1;
        a = a.pow(K - N);
        for (int i = 0; i < N; i++)
            if (a[0][i].val()) ans ^= A[N - i - 1];
        cout << ans << "\n";
    }
    return 0;
}
0