Submission #1033199

Source Code Expand

N = input()
MOD = 10**9+7

memo = {0: 1, 1: 2}
def S(k):
    if k in memo:
        return memo[k]
    if k % 2 == 1:
        result = (2*S(k/2) + S(k/2-1)) % MOD
    else:
        result = (S(k/2) + 2*S(k/2-1)) % MOD
    memo[k] = result
    return result
print S(N)

Submission Info

Submission Time
Task D - Xor Sum
User yaketake08
Language Python (2.7.6)
Score 600
Code Size 279 Byte
Status AC
Exec Time 17 ms
Memory 2692 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 16
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All 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 17 ms 2568 KB
sample_02.txt AC 17 ms 2568 KB
sample_03.txt AC 17 ms 2568 KB
subtask_1_max_01.txt AC 17 ms 2568 KB
subtask_1_rand_01.txt AC 17 ms 2568 KB
subtask_1_rand_02.txt AC 17 ms 2568 KB
subtask_1_rand_03.txt AC 17 ms 2568 KB
subtask_1_rand_04.txt AC 17 ms 2568 KB
subtask_1_rand_05.txt AC 17 ms 2692 KB
subtask_1_small_rand_01.txt AC 17 ms 2568 KB
subtask_1_small_rand_02.txt AC 17 ms 2568 KB
subtask_1_small_rand_03.txt AC 17 ms 2568 KB
subtask_1_small_rand_04.txt AC 17 ms 2568 KB
subtask_1_small_rand_05.txt AC 17 ms 2568 KB
subtask_1_specific_01.txt AC 17 ms 2568 KB
subtask_1_specific_02.txt AC 17 ms 2568 KB
subtask_1_specific_03.txt AC 17 ms 2568 KB
subtask_1_specific_04.txt AC 17 ms 2568 KB
subtask_1_specific_05.txt AC 17 ms 2568 KB