Submission #1607274

---

Source Code Expand

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

vector<vector<size_t>> mul(const vector<vector<size_t>> &T1, const vector<vector<size_t>> &T2){
    int K = T1.size();
    vector<vector<size_t>> T(K, vector<size_t>(K, 0));
    for(int i=0; i<K; i++)
        for(int j=0; j<K; j++)
            for(int k=0; k<K; k++)
                T[i][j] ^= T1[i][k] & T2[k][j];
    return T;
}

vector<vector<size_t>> bipow(const vector<vector<size_t>> &T, int m){
    if(m == 1) return T;
    if(m % 2 == 0){
        auto T2 = mul(T, T);
        return bipow(T2, m/2);
    }
    return mul(T, bipow(T, m-1));
}

vector<size_t> vec(const vector<vector<size_t>> &T, const vector<size_t> x){
    int K = x.size();
    vector<size_t> y(K, 0);
    for(int i=0; i<K; i++)
        for(int j=0; j<K; j++)
            y[i] ^= T[i][j] & x[j];
    return y;
}

int main(){
    int K, M;
    cin >> K >> M;
    vector<size_t> A(K), C(K);
    for(int i=0; i<K; i++) cin >> A[i];
    for(int i=0; i<K; i++) cin >> C[i];
    if(M <= K){
        cout << A[M-1] << endl;
        return 0;
    }
    reverse(A.begin(), A.end());

    vector<vector<size_t>> T(K, vector<size_t>(K, 0));
    for(int i=0; i<K; i++) T[0][i] = C[i];
    for(int i=1; i<K; i++) T[i][i-1] = UINT_MAX;;

    auto T2 = bipow(T, M-K);
    auto x = vec(T2, A);
    cout << x[0] << endl;
    return 0;
}

Submission Info

Judge Result