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
AC × 17
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