Submission #8567969

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int MAXBIT = 60;
const long long MOD = 1E9+7;

long long f[MAXBIT+2][2][2];

long long n;

long long dp(int i, int mod, bool ok){
	long long& ret = f[i][mod][ok];
	if(ret != -1) return ret;
	if(i == MAXBIT) return ret = (mod == 0 && ok == 0);
	int bitn = (n>>i)&1;
	ret = 0;
	for(int a = 0; a < 2; ++a)
		for(int b = 0; b <=a ; ++b){
			int curbit = (a+b+mod)%2;
			int nmod = (a+b+mod)/2;
			bool nok = ok;
			if(curbit > bitn) nok = 1;
			if(curbit < bitn) nok = 0;
			ret += dp(i+1, nmod, nok);
			ret %= MOD;
 		}
 	return ret;
}

int main() {
	cin >> n;
	memset(f, -1, sizeof f);
	cout << dp(0,0, 0);
	return 0;
}

Submission Info

Submission Time
Task D - Xor Sum
User tRuNgSeO
Language C++14 (GCC 5.4.1)
Score 600
Code Size 705 Byte
Status AC
Exec Time 1 ms
Memory 256 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 19
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_max_01.txt, subtask_1_rand_01.txt, subtask_1_rand_02.txt, subtask_1_rand_03.txt, subtask_1_rand_04.txt, subtask_1_rand_05.txt, subtask_1_small_rand_01.txt, subtask_1_small_rand_02.txt, subtask_1_small_rand_03.txt, subtask_1_small_rand_04.txt, subtask_1_small_rand_05.txt, subtask_1_specific_01.txt, subtask_1_specific_02.txt, subtask_1_specific_03.txt, subtask_1_specific_04.txt, subtask_1_specific_05.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KiB
sample_02.txt AC 1 ms 256 KiB
sample_03.txt AC 1 ms 256 KiB
subtask_1_max_01.txt AC 1 ms 256 KiB
subtask_1_rand_01.txt AC 1 ms 256 KiB
subtask_1_rand_02.txt AC 1 ms 256 KiB
subtask_1_rand_03.txt AC 1 ms 256 KiB
subtask_1_rand_04.txt AC 1 ms 256 KiB
subtask_1_rand_05.txt AC 1 ms 256 KiB
subtask_1_small_rand_01.txt AC 1 ms 256 KiB
subtask_1_small_rand_02.txt AC 1 ms 256 KiB
subtask_1_small_rand_03.txt AC 1 ms 256 KiB
subtask_1_small_rand_04.txt AC 1 ms 256 KiB
subtask_1_small_rand_05.txt AC 1 ms 256 KiB
subtask_1_specific_01.txt AC 1 ms 256 KiB
subtask_1_specific_02.txt AC 1 ms 256 KiB
subtask_1_specific_03.txt AC 1 ms 256 KiB
subtask_1_specific_04.txt AC 1 ms 256 KiB
subtask_1_specific_05.txt AC 1 ms 256 KiB