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 |
|
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 |