Submission #4066220


Source Code Expand

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

template <typename T>
vector<T> DotMatrix(const vector<vector<T>>& a, const vector<T>& x){
    vector<T> ret(x.size(), 0);
    for (size_t i = 0; i < a.size(); ++i) {
		for (int j = 0; j < x.size(); ++j) {
			ret[i] ^= (a[i][j] & x[j]);
		}
    }
    return ret;
}

template <typename T>
vector<vector<T>> DotMatrix(const vector<vector<T>>& a, const vector<vector<T>>& b){
    vector<vector<T>> ret(a.size(), vector<T>(b[0].size(), 0));
    for (size_t i = 0; i < ret.size(); ++i) {
		for (size_t j = 0; j < ret[i].size(); ++j) {
			for (size_t k = 0; k < b.size(); ++k) {
				ret[i][j] ^= (a[i][k] & b[k][j]);
			}
		}
	}
    return ret;
}

int main() {
	ll K, M;
	cin >> K >> M;
	vector<ll> a(K);
	vector<ll> c(K);
	for (int i = 0; i < K; ++i) { cin >> a[i]; }
	for (int i = 0; i < K; ++i) { cin >> c[i]; }
	reverse(a.begin(), a.end());

	if (M <= K) {
		cout << a[M - 1] << endl;
		return 0;
	}
	M = M - K;

	vector<vector<ll>> mat(K, vector<ll>(K, 0));
	for (int i = 0; i < K; ++i) {
		if (i == 0) {
			for (int j = 0; j < K; ++j) {
				mat[i][j] = c[j];
			}
		} else {
			mat[i][i - 1] = (1LL << 32) - 1;
		}
	}

	int idk = 0;
	while (pow(2, idk) <= M) { ++idk; }
	vector<vector<vector<ll>>> table(idk + 1, vector<vector<ll>>(K, vector<ll>(K)));
	table[0] = mat;
	for (int i = 1; i <= idk; ++i) {
		table[i] = DotMatrix(table[i - 1], table[i - 1]);
	}

	vector<ll> res = a;
	for (int i = 0; i <= idk; ++i) {
		if ((M>>i) & 1) {
			res = DotMatrix(table[i], res);
		}
	}
	cout << res[0] << endl;

	return 0;
}

Submission Info

Submission Time
Task D - 漸化式
User woodline23xx
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1658 Byte
Status WA
Exec Time 35 ms
Memory 2944 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 17
WA × 3
Set Name Test Cases
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, sample_1.txt, sample_2.txt, sample_3.txt, small_1.txt, small_2.txt
Case Name Status Exec Time Memory
random_01.txt AC 1 ms 256 KB
random_02.txt AC 1 ms 256 KB
random_03.txt WA 1 ms 256 KB
random_04.txt WA 1 ms 256 KB
random_05.txt WA 1 ms 256 KB
random_06.txt AC 1 ms 256 KB
random_07.txt AC 3 ms 512 KB
random_08.txt AC 6 ms 1024 KB
random_09.txt AC 34 ms 2816 KB
random_10.txt AC 35 ms 2944 KB
random_11.txt AC 35 ms 2944 KB
random_12.txt AC 35 ms 2944 KB
random_13.txt AC 35 ms 2944 KB
random_14.txt AC 35 ms 2944 KB
random_15.txt AC 34 ms 2816 KB
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 2 ms 512 KB
small_1.txt AC 1 ms 256 KB
small_2.txt AC 1 ms 256 KB