Submission #1602376
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vec; typedef vector<vec> mat; const ll INF = (1LL << 40) - 1; mat mul(mat &A, mat &B) { mat C(A.size(), vec(B[0].size())); for (int i = 0; i < A.size(); i++) { for (int k = 0; k < B.size(); k++) { for (int j = 0; j < B[0].size(); j++) { C[i][j] ^= A[i][k] & B[k][j]; } } } return C; } mat pow(mat A, int n) { mat B(A.size(), vec(A.size())); for (int i = 0; i < A.size(); i++) { B[i][i] = INF; } while (n > 0) { if (n & 1) B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } int main(void) { int K, M; cin >> K >> M; vector<ll> a(K), c(K); for (int i = 0; i < K; i++) { cin >> a[i]; } for (int i = 0; i < K; i++) { cin >> c[i]; } mat A(K, vec(K)); for (int i = 0; i < K; i++) { for (int j = 0; j < K; j++) { if (i == 0) { A[i][j] = c[j]; } else if (j == i - 1) { A[i][j] = INF; } } } A = pow(A, M - K); ll ans = 0; for (int i = 0; i < K; i++) { ans ^= A[0][i] & a[K - i - 1]; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 漸化式 |
User | legosuke |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1223 Byte |
Status | WA |
Exec Time | 51 ms |
Memory | 640 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 | AC | 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 | 256 KB |
random_08.txt | AC | 8 ms | 384 KB |
random_09.txt | AC | 49 ms | 512 KB |
random_10.txt | AC | 51 ms | 512 KB |
random_11.txt | AC | 50 ms | 512 KB |
random_12.txt | AC | 50 ms | 640 KB |
random_13.txt | AC | 51 ms | 512 KB |
random_14.txt | AC | 50 ms | 640 KB |
random_15.txt | AC | 47 ms | 512 KB |
sample_1.txt | AC | 1 ms | 256 KB |
sample_2.txt | AC | 1 ms | 256 KB |
sample_3.txt | AC | 2 ms | 256 KB |
small_1.txt | AC | 1 ms | 256 KB |
small_2.txt | AC | 1 ms | 256 KB |