Submission #343281
Source Code Expand
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
#define LL long long
LL M;
LL a[33][2 * 1000];
LL a0[1000];
LL c[1000];
//a(0)からa(2*m-2)の形のa(n)をa(0)からa(m-1)の形に直す
void form(LL* n){
rev(i, M+1, 2 * M + 1){
rep(j, 1, M + 1)
n[i - j] = (n[i - j] ^ (c[M - j] & n[i]));
n[i] = 0;
}
}
void print(LL *result){
rep(i, 0, 2*M){
printf("%lld ", result[i+1]);
}
cout << endl;
}
void add(LL *l, LL *r, LL *ans){
//print(l); print(r);
rep(i, 1, 2 * M +1){
ans[i] = 0;
}
rep(i, 1, M+1)
rep(j, 1, M+1){
ans[i + j] = (ans[i + j] ^ (l[i] & r[j])) ;
}
// print(ans);
form(ans);
// print(ans);
}
void init(){
a[0][1] = 1;
rep(i, 0, 40)a[0][1] <<= 1;
a[0][1] -= 1;
}
LL calc(int n){
LL result[2000] = {0, a[0][1] };
LL tmp[2000] = { 0,a[0][1] };
int bin = 0;
while (n){
if (1 & n){
add(tmp, a[bin], result);
rep(j, 1, M+1)tmp[j] = result[j];
}
n >>= 1;
add(a[bin], a[bin], a[bin + 1]);
bin++;
// printf("[%d]", bin-1); print(a[bin-1]);
}
LL ans = 0;
rep(i, 0, M)
ans = (ans ^ (result[i+1] & a0[i]));
return(ans);
}
int main(void){
int n;
cin >> M >> n;
rep(i, 0, M){
cin >> a0[i];
}
rev(i, 0, M){
cin >> c[i];
}
init();
cout << calc(n-1) << endl;
}
Submission Info
Submission Time |
|
Task |
D - 漸化式 |
User |
btk15049 |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
1437 Byte |
Status |
AC |
Exec Time |
31 ms |
Memory |
1184 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, small_1.txt, small_2.txt |
Case Name |
Status |
Exec Time |
Memory |
random_01.txt |
AC |
28 ms |
1088 KB |
random_02.txt |
AC |
26 ms |
1004 KB |
random_03.txt |
AC |
25 ms |
1052 KB |
random_04.txt |
AC |
29 ms |
1004 KB |
random_05.txt |
AC |
27 ms |
880 KB |
random_06.txt |
AC |
26 ms |
964 KB |
random_07.txt |
AC |
28 ms |
1176 KB |
random_08.txt |
AC |
27 ms |
1088 KB |
random_09.txt |
AC |
29 ms |
1184 KB |
random_10.txt |
AC |
30 ms |
1072 KB |
random_11.txt |
AC |
30 ms |
1096 KB |
random_12.txt |
AC |
31 ms |
1176 KB |
random_13.txt |
AC |
31 ms |
1164 KB |
random_14.txt |
AC |
31 ms |
1128 KB |
random_15.txt |
AC |
29 ms |
1180 KB |
sample_1.txt |
AC |
28 ms |
1012 KB |
sample_2.txt |
AC |
28 ms |
964 KB |
sample_3.txt |
AC |
29 ms |
1132 KB |
small_1.txt |
AC |
29 ms |
1128 KB |
small_2.txt |
AC |
29 ms |
1128 KB |