Submission #1779311

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
using matrix = vector<vector<ll> >;
matrix E;
matrix po(matrix &a, matrix &b){
	matrix ret;
	for(ll i = 0; i < a.size(); ++i){
		vector<ll> yo;
		for(ll j = 0; j < b[0].size(); ++j){
			ll c = 0;
			for(ll k = 0; k < b.size(); ++k)c ^= (a[i][k] & b[k][j]);
			yo.push_back(c);
		}
		ret.push_back(yo);
	}
	return ret;
}
matrix pow(matrix &a, ll b){
	matrix yo[30] = {a};
	for(ll i = 1; i < 30; ++i) yo[i] = po(yo[i - 1], yo[i - 1]);
	matrix ret = E;
	for(ll i = 0; b; ++i){
		if(b & 1) ret = po(yo[i], ret);
		b /= 2;
	}
	return ret;
}
int main(){
	ll k, m; cin >> k >> m;
	ll a[k], c[k];
	ll anabi = (ll)pow(2, 32) - 1;
	for(ll i = 0; i < 2 * k; ++i) cin >> (i / k ? c : a)[i % k];
	for(ll i = 0; i < k; ++i){
		vector<ll> yo;
		for(ll j = 0; j < k; ++j) yo.push_back((i == j ? anabi : 0));
		E.push_back(yo);
	}
	matrix sina, pomu;
	vector<ll> mon;
	for(ll i = 0; i < k; ++i){
		mon.push_back(c[i]);
		vector<ll> purin;
		purin.push_back(a[k - 1 - i]);
		pomu.push_back(purin);
	}
	sina.push_back(mon);
	for(ll i = 1; i < k; ++i){
		vector<ll> pinya;
		for(ll j = 0; j < k; ++j)pinya.push_back((i - 1 == j ? anabi : 0));
		sina.push_back(pinya);
	}
	matrix temp = pow(sina, m - k);
	matrix ans = po(temp, pomu);
	cout << ans[0][0] << endl;
	return 0;
}

Submission Info

Judge Result