Submission #1607712
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>bool chmin(T&a,const T&b){return a>b?(a=b,1):0;}
template<class T>bool chmax(T&a,const T&b){return a<b?(a=b,1):0;}
ll nextLL() { ll x; cin >> x; return x; }
#define SZ(v) ((int)(v).size())
typedef vector<ll> Array;
typedef vector<Array> Matrix;
Matrix zero(int N){ return Matrix(N, Array(N)); }
Matrix identity(int N) {
Matrix A = zero(N);
REP(i, N) A[i][i] = 1;
return A;
}
Array mul(const Matrix &A, const Array &x){
const int N = SZ(A);
const int M = SZ(A[0]);
Array y(N);
REP(i, N) REP(j, M) {
y[i] += A[i][j] * x[j];
y[i] = y[i] & 1;
}
return y;
}
Matrix mul(const Matrix &A, const Matrix& B) {
const int N = SZ(A);
const int P = SZ(A[0]);
const int M = SZ(B[0]);
Matrix C(N, Array(M));
REP(i, N) REP(j, M) REP(k, P) {
C[i][j] += A[i][k] * B[k][j];
C[i][j] = C[i][j] & 1;
}
return C;
}
Matrix pow(Matrix A, ll b) {
Matrix C = identity(SZ(A));
while (b > 0) {
if ((b & 1) == 1) C = mul(C, A);
A = mul(A, A);
b >>= 1;
}
return C;
}
int g = 0;
int main2() {
int K = (int)nextLL();
int M = (int)nextLL();
vector<ll> A(K), C(K);
REP(i, K) A[i] = nextLL();
REP(i, K) C[i] = nextLL();
if (M <= K) {
cout << A[M-1] << endl;
return 0;
}
ll ans = 0;
for (int bit = 0; bit < 32; bit++) {
Matrix P = zero(K);
REP(i, K - 1) P[i][i+1] = 1;
REP(j, K) P[K-1][j] = (C[K - 1 - j] >> bit) & 1;
Array a = Array(K);
REP(i, K) a[i] = (A[i] >> bit) & 1;
P = pow(P, M - K);
a = mul(P, a);
ans |= a[K-1] * (1LL << bit);
}
cout << ans << endl;
return 0;
}
int main() {
for ( ; !cin.eof(); cin >> ws) main2();
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 漸化式 |
User |
hs484 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2126 Byte |
Status |
AC |
Exec Time |
1792 ms |
Memory |
632 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 |
2 ms |
256 KB |
random_02.txt |
AC |
2 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 |
67 ms |
256 KB |
random_08.txt |
AC |
248 ms |
384 KB |
random_09.txt |
AC |
1719 ms |
576 KB |
random_10.txt |
AC |
1792 ms |
632 KB |
random_11.txt |
AC |
1791 ms |
624 KB |
random_12.txt |
AC |
1792 ms |
632 KB |
random_13.txt |
AC |
1791 ms |
632 KB |
random_14.txt |
AC |
1791 ms |
632 KB |
random_15.txt |
AC |
1674 ms |
632 KB |
sample_1.txt |
AC |
1 ms |
256 KB |
sample_2.txt |
AC |
1 ms |
256 KB |
sample_3.txt |
AC |
48 ms |
256 KB |
small_1.txt |
AC |
1 ms |
256 KB |
small_2.txt |
AC |
1 ms |
256 KB |