Submission #7088695
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define int long long const int MAX = 1001; const int MOD = 1000000007; signed main(){ int n; cin>>n; int k=0,o=1; while(n>=(o<<k))k++; int dp[k][3]; dp[0][0]=1; dp[0][1]=1; dp[0][2]=0; for(int i=1;i<k;i++){ if(1&(n>>(k-i-1))){ dp[i][0]=dp[i-1][0]; dp[i][1]=(dp[i-1][0]+dp[i-1][1])%MOD; dp[i][2]=(dp[i-1][2]*3+dp[i-1][1]*2)%MOD; }else{ dp[i][0]=(dp[i-1][0]+dp[i-1][1])%MOD; dp[i][1]=dp[i-1][1]; dp[i][2]=(dp[i-1][2]*3+dp[i-1][1])%MOD; } } cout<<(dp[k-1][0]+dp[k-1][1]+dp[k-1][2])%MOD; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Xor Sum |
User | yatuba |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 727 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 |