Submission #1217917

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int BASE=1e9+7;

long long N,f[100][2][2][2];

long long dp(int bit, int carry, int isA, int isB)
{
    if (bit==63)
    {
        if (carry==0) return (!isA && !isB);
        else
        {
            if (N>>bit&1) return (!isA && !isB);
            else return 0;
        }
    }
    if (f[bit][carry][isA][isB]==-1)
    {
        f[bit][carry][isA][isB]=0;
        bool nxA,nxB;
        int bitA,bitB,ncarry;
        // bit u^v= 0 && u+v=0
        bitA=carry;
        bitB=0;
        ncarry=0;
        if (N>>bit&1)
        {
            if (bitA) nxA=isA;
            else nxA=0;
            nxB=0;
        }
        else
        {
            if (bitA) nxA=1;
            else nxA=isA;
            nxB=isB;
        }
        f[bit][carry][isA][isB]+=dp(bit+1,ncarry,nxA,nxB);
        f[bit][carry][isA][isB]%=BASE;
        // bit u^v= 1
        bitA=(carry+1)%2;
        ncarry=(carry+1)/2;
        bitB=1;
        if (N>>bit&1)
        {
            if (bitA) nxA=isA;
            else nxA=0;
            nxB=isB;
        }
        else
        {
            if (bitA) nxA=1;
            else nxA=isA;
            nxB=1;
        }
        f[bit][carry][isA][isB]+=dp(bit+1,ncarry,nxA,nxB);
        f[bit][carry][isA][isB]%=BASE;
        // bit u^v=0 && u+v=1
        bitA=carry;
        ncarry=1;
        bitB=0;
        if (N>>bit&1)
        {
            if (bitA) nxA=isA;
            else nxA=0;
            nxB=0;
        }
        else
        {
            if (bitA) nxA=1;
            else nxA=isA;
            nxB=isB;
        }
        f[bit][carry][isA][isB]+=dp(bit+1,ncarry,nxA,nxB);
        f[bit][carry][isA][isB]%=BASE;
    }
    return f[bit][carry][isA][isB];
}

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

Submission Info

Judge Result