Submission #1112649

---

Source Code Expand

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i = (a);i<(b);i++)
#define ROF(i,a,b) for(int i = (a);i>(b);i--)
#define MST(a,x) memset(a,x,sizeof(a))
#define ll long long
#define PB push_back
#define PH push
#define MP make_pair
#define FT first
#define SD second
#define N 70
#define M 51
#define INF 1000000007
#define MOD 1000000007
#define MOD2 1000000009
#define eps 1e-14
using namespace std;
inline int Max(int a,int b)
{
    return (((b-a)>>(32-1))&(a^b))^b;
}
inline int Min(int a,int b)
{
    return (((b-a)>>(32-1))&(a^b))^a;
}

ll dp[N][2][2];
int bit[N];
int main()
{
    ll n;
    while(cin>>n)
    {
        int id = 0;
        while(n)
        {
            bit[++id] = n%2;
            n>>=1;
        }
        MST(dp,0);
        dp[0][0][0] = 1;
        FOR(i,1,id+1)
        {
            if(bit[i] == 0)
            {
                dp[i][0][0] = dp[i-1][0][0];
                dp[i][0][1] = (dp[i-1][0][0]+2*dp[i-1][0][1]+dp[i-1][1][0]+dp[i-1][1][1])%MOD;
                dp[i][1][0] = (dp[i-1][0][0]+dp[i-1][1][0])%MOD;
                dp[i][1][1] = (dp[i-1][0][1]+dp[i-1][1][0]+2*dp[i-1][1][1])%MOD;
            }
            else
            {
                dp[i][0][0] = (2*dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][1][0])%MOD;
                dp[i][0][1] = (dp[i-1][0][1]+dp[i-1][1][1])%MOD;
                dp[i][1][0] = (dp[i-1][0][0]+dp[i-1][0][1]+2*dp[i-1][1][0]+dp[i-1][1][1])%MOD;
                dp[i][1][1] = dp[i-1][1][1];
            }
        }
        cout<<dp[id][0][0]<<endl;
    }
    return 0;
}

Submission Info

Judge Result