Submission #2176453
Source Code Expand
#include<iostream> #include<iomanip> //#include<cstdio> #include<vector> #include<map> #include<queue> #include<algorithm> #include<cmath> #include<cassert> using namespace std; typedef long long ll; const int Kmax = 100; ll A[Kmax], C[Kmax], M; int K; void matmul(vector<vector<ll> > &a, vector<vector<ll> > &b, vector<vector<ll> > &c){ for(int i=0; i<K; i++){ for(int j=0; j<K; j++){ c[i][j] = 0; for(int k=0; k<K; k++){ c[i][j] = c[i][j] ^ (a[i][k] & b[k][j]); } } } } void matpow(vector<vector<ll> > &a, ll n, vector<vector<ll> > &x){ if(n == 0) { for(int i=0; i<K; i++){ for(int j=0; j<K; j++){ if(i==j) x[i][j] = (1ll<<32)-1; else x[i][j] = 0; } } return; } if(n == 1) { for(int i=0; i<K; i++){ for(int j=0; j<K; j++){ x[i][j] = a[i][j]; } } return; } vector<vector<ll> > tmp(K, vector<ll>(K)); if(n%2 == 0) { matpow(a, n/2, tmp); matmul(tmp, tmp, x); } else { matpow(a, n-1, tmp); matmul(tmp, a, x); } } int main(){ cin >> K >> M; for(int i=0; i<K; i++) cin >> A[i]; for(int i=0; i<K; i++) cin >> C[i]; if(M <= K){ cout << A[M-1] << endl; return 0; } vector<vector<ll> > mat(K, vector<ll>(K)); for(int i=0; i<K; i++){ mat[0][i] = C[i]; } for(int i=0; i<K-1; i++){ mat[i+1][i] = (1ll<<32)-1; } //for(int i=0; i<K; i++){ // for(int j=0; j<K; j++){ // cout << mat[i][j] << (j==K-1?'\n':' '); // } //} vector<vector<ll> > mat2(K, vector<ll>(K)); matpow(mat, M-K, mat2); //for(int i=0; i<K; i++){ // for(int j=0; j<K; j++){ // cout << mat2[i][j] << (j==K-1?'\n':' '); // } //} ll ans = 0; for(int i=0; i<K; i++){ ans = ans ^ (A[i] & mat2[0][K-i-1]); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - 漸化式 |
User | emak |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1705 Byte |
Status | AC |
Exec Time | 50 ms |
Memory | 4096 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 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 | AC | 1 ms | 256 KB |
random_04.txt | AC | 1 ms | 256 KB |
random_05.txt | AC | 1 ms | 256 KB |
random_06.txt | AC | 1 ms | 256 KB |
random_07.txt | AC | 3 ms | 640 KB |
random_08.txt | AC | 8 ms | 1280 KB |
random_09.txt | AC | 49 ms | 3968 KB |
random_10.txt | AC | 50 ms | 4096 KB |
random_11.txt | AC | 50 ms | 4096 KB |
random_12.txt | AC | 50 ms | 4096 KB |
random_13.txt | AC | 50 ms | 4096 KB |
random_14.txt | AC | 50 ms | 4096 KB |
random_15.txt | AC | 47 ms | 3840 KB |
sample_1.txt | AC | 1 ms | 256 KB |
sample_2.txt | AC | 1 ms | 256 KB |
sample_3.txt | AC | 3 ms | 640 KB |
small_1.txt | AC | 1 ms | 256 KB |
small_2.txt | AC | 1 ms | 256 KB |