Submission #1112576


Source Code Expand

#include <bits/stdc++.h>
#define DEBUG(x) cout << #x << " = " << x << endl
#define pb push_back
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
map <ll, ll> F_mem;
map <ll, ll> f_mem;

ll add(ll a, ll b)
{
    return (a + b) % MOD;
}

ll mult(ll a, ll b)
{
    return (a*b) % MOD;
}

ll f(ll N)
{
    if (f_mem.find(N) != f_mem.end())
    {
        return f_mem[N];
    }

    ll res;
    if (N == 0) res = 1;
    else if (N == 1) res = 1;
    else if (N % 2 == 1) res = f(N/2);
    else if (N % 2 == 0) res = add(f(N/2), f(N/2-1));

    return f_mem[N] = res;
}

ll F (ll N)
{
    if (F_mem.find(N) != F_mem.end())
    {
        return F_mem[N];
    }

    ll res;
    if (N == 0) res = 1;
    else if (N == 1) res = 2;
    else if (N % 2 == 1) res = add(mult(2,f(N/2)),mult(3,F(N/2-1)));
    else if (N % 2 == 0) res = add(f(N/2), mult(3,F(N/2-1)));

    return F_mem[N] = res;
}


int main()
{
    //freopen("input.txt", "r", stdin);
    ll N;
    cin >> N;
    cout << F(N);


    return 0;
}

Submission Info

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

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 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