Submission #3596254
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define REP(i, a, n) for (int i = (a); i < (int)(n); i++) #define rep(i, n) REP(i, 0, n) #define FOR(it, c) \ for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; static const ll MOD = 1000000007LL; ll dp[64][3]; int main() { ll N; cin >> N; dp[63][0] = 1; for (ll i = 62; i >= 0; i--) { if (((N >> i) & 1) == 0) { dp[i][0] += dp[i + 1][0]; dp[i][0] %= MOD; dp[i][0] += dp[i + 1][1]; dp[i][0] %= MOD; dp[i][1] += dp[i + 1][1]; dp[i][1] %= MOD; dp[i][2] += dp[i + 1][1]; dp[i][2] %= MOD; dp[i][2] += dp[i + 1][2] * 3; dp[i][2] %= MOD; } else { dp[i][0] += dp[i + 1][0]; dp[i][0] %= MOD; dp[i][1] += dp[i + 1][0]; dp[i][1] %= MOD; dp[i][1] += dp[i + 1][1]; dp[i][1] %= MOD; dp[i][2] += dp[i + 1][1] * 2; dp[i][2] %= MOD; dp[i][2] += dp[i + 1][2] * 3; dp[i][2] %= MOD; } } ll ret = 0; rep(i, 3) { ret += dp[0][i]; ret %= MOD; } cout << ret << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Xor Sum |
User | phyllo |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1245 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
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 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
subtask_1_max_01.txt | AC | 1 ms | 256 KB |
subtask_1_rand_01.txt | AC | 1 ms | 256 KB |
subtask_1_rand_02.txt | AC | 1 ms | 256 KB |
subtask_1_rand_03.txt | AC | 1 ms | 256 KB |
subtask_1_rand_04.txt | AC | 1 ms | 256 KB |
subtask_1_rand_05.txt | AC | 1 ms | 256 KB |
subtask_1_small_rand_01.txt | AC | 1 ms | 256 KB |
subtask_1_small_rand_02.txt | AC | 1 ms | 256 KB |
subtask_1_small_rand_03.txt | AC | 1 ms | 256 KB |
subtask_1_small_rand_04.txt | AC | 1 ms | 256 KB |
subtask_1_small_rand_05.txt | AC | 1 ms | 256 KB |
subtask_1_specific_01.txt | AC | 1 ms | 256 KB |
subtask_1_specific_02.txt | AC | 1 ms | 256 KB |
subtask_1_specific_03.txt | AC | 1 ms | 256 KB |
subtask_1_specific_04.txt | AC | 1 ms | 256 KB |
subtask_1_specific_05.txt | AC | 1 ms | 256 KB |