Submission #1306498

---

Source Code Expand

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

typedef vector<unsigned int> vec;
typedef vector<vec> mat;

mat mul(mat a, mat b) {
	mat c(a.size(), vec(b[0].size()));

	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < b[0].size(); j++) {
			for (int k = 0; k < a[0].size(); k++) {
				c[i][j] ^= (a[i][k] & b[k][j]);
			}
		}
	}

	return c;
}

mat pow(int x, mat a) {
	//cout << x << endl;

	if (x == 1)return a;

	mat b;
	if (x / 2 == 1)b = mul(a, a);
	else {
		b = pow(x / 2, a);
		b = mul(b, b);
	}

	if (x % 2 != 1) {
		b = mul(a, b);
	}

	return b;
}

void display(mat a) {
	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < a[0].size(); j++) {
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

int main() {
	int k, m;
	cin >> k >> m;

	mat a(k, vec(1));
	mat c(k, vec(k));
	for (int i = k-1; i >= 0; i--) {
		cin >> a[i][0];
	}

	for (int i = 0; i < k; i++) {
		for (int j = 0; j < k; j++) {
			if (j > 0 && j == i) {
				c[i][j - 1] = UINT32_MAX;
			}
			else {
				c[i][j] = 0;
			}
		}
		cin >> c[0][i];
	}

	/*display(a);
	cout << endl;
	display(c);*/

	if (k >= m) {
		cout << a[k - 1][0] << endl;
	}
	else {
		mat b = pow(m - k+1, c);
		mat ans = mul(b, a);
		cout << ans[0][0] << endl;
	}
}

Submission Info

Judge Result