結果

問題 No.64 XORフィボナッチ数列
コンテスト
ユーザー gemy
提出日時 2023-11-23 12:46:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 4,319 bytes
コンパイル時間 2,185 ms
コンパイル使用メモリ 198,952 KB
最終ジャッジ日時 2025-02-17 23:13:33
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
// N 次正方行列 Matrix
template <class T> class Matrix {
private:
    // 成分
    vector<vector<T>> c;
    // 次数
    int size;
public:
    // ゼロ行列で初期化
    Matrix(int size) : size(size), c(size, vector<T>(size)) {}
    // 与えられた成分をもつ行列で初期化
    Matrix(vector<vector<T>>& v) : c(v), size(v.size()) {}
    // スカラー行列 (デフォルトで単位行列)
    static Matrix identity(int size, T a = numeric_limits<long long>::max()) {
        Matrix A(size);
        for (int i = 0; i < size; ++i) A.c[i][i] = a;
        return A;
    }
    // 行列式
    T det() const {
        int p[size];
        for (int i = 0; i < size; ++i) p[i] = i;
        T ret = 0;
        do {
            int sign = 1;
            for (int i = 0; i < size; ++i) {
                for (int j = i + 1; j < size; ++j) {
                    if (p[i] > p[j]) sign *= -1;
                }
            }
            T temp = 1;
            for (int i = 0; i < size; ++i) temp *= c[i][p[i]];
            ret += sign * temp;
        } while (next_permutation(p, p + size));
        return ret;
    }
    // 足し算
    Matrix operator+(const Matrix& A) const {
        Matrix B(size);
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < size; ++j) {
                B.c[i][j] = c[i][j] + A.c[i][j];
            }
        }
        return B;
    }
    // 引き算
    Matrix operator-(const Matrix& A) const {
        Matrix B(size);
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < size; ++j) {
                B.c[i][j] = c[i][j] - A.c[i][j];
            }
        }
        return B;
    }
    // 掛け算
    Matrix operator*(const Matrix& A) const {
        Matrix B(size);
        for (int i = 0; i < size; ++i) {
            for (int k = 0; k < size; ++k) {
                for (int j = 0; j < size; ++j) {
                    B.c[i][j] ^= c[i][k] & A.c[k][j];
                }
            }
        }
        return B;
    }
    // スカラー倍
    Matrix operator*(T a) const {
        Matrix B(size);
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < size; ++j) {
                B.c[i][j] = a * c[i][j];
            }
        }
        return B;
    }
    // マイナス倍
    Matrix operator-() const { return Matrix(size) - *this; }
    // 自分自身への足し算
    Matrix& operator+=(const Matrix& A) { *this = *this + A; return *this; }
    // 自分自身への引き算
    Matrix& operator-=(const Matrix& A) { *this = *this - A; return *this; }
    // 自分自身への掛け算
    Matrix& operator*=(const Matrix& A) { *this = *this * A; return *this; }
    // 自分自身へのスカラー倍
    Matrix& operator*=(T a) { *this = *this * a; return *this; }
    // 等号判定
    bool operator==(const Matrix& A) const { return c == A.c; }
    // 累乗
    Matrix pow(T n) const {
        if (n == 0) return identity(size);
        if (n & 1) return (*this) * ((*this) * (*this)).pow(n / 2);
        return ((*this) * (*this)).pow(n / 2);
    }
    // 出力
    friend ostream& operator<<(ostream& os, const Matrix& A) {
        for (int i = 0; i < A.size; ++i) {
            if (i > 0) os << '\n';
            for (int j = 0; j < A.size; ++j) {
                if (j > 0) os << ' ';
                os << A.c[i][j];
            }
        }
        return os;
    }
    // 入力
    friend istream& operator>>(istream& is, Matrix& A) {
        for (int i = 0; i < A.size; ++i) {
            for (int j = 0; j < A.size; ++j) {
                is >> A.c[i][j];
            }
        }
        return is;
    }
    // 添字でのアクセス
    vector<T>& operator[](int i) { return c[i]; }
    // 添字でのアクセス
    const vector<T>& operator[](int i) const { return c[i]; }
};
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
int main() {
    // Input
    long long F0, F1, N;
    cin >> F0 >> F1 >> N;

    // Trivial Case
    if (N == 0) {
        cout << F0 << endl;
        return 0;
    }

    // Calculation
    Matrix<long long> A(2), P(2);
    A[0][0] = A[0][1] = A[1][0] = LONG_LONG_MAX;
    P = A.pow(N - 1);

    // Output
    long long ans = (F1 & P[0][0]) ^ (F0 & P[0][1]);
    cout << ans << endl;
}
0