Xor Sum（AtCoder-2272）

Problem Description

You are given a positive integer N. Find the number of the pairs of integers u and v (0≦u,v≦N) such that there exist two non-negative integers a and b satisfying a xor b=u and a+b=v. Here, xor denotes the bitwise exclusive OR. Since it can be extremely large, compute the answer modulo 109+7.

Constraints

• 1≦N≦10^18

Input

The input is given from Standard Input in the following format:

N

Output

Print the number of the possible pairs of integers u and v, modulo 109+7.

Example

Sample Input 1

3

Sample Output 1

5

The five possible pairs of u and v are:

u=0,v=0 (Let a=0,b=0, then 0 xor 0=0, 0+0=0.)

u=0,v=2 (Let a=1,b=1, then 1 xor 1=0, 1+1=2.）

u=1,v=1 (Let a=1,b=0, then 1 xor 0=1, 1+0=1.）

u=2,v=2 (Let a=2,b=0, then 2 xor 0=2, 2+0=2.）

u=3,v=3 (Let a=3,b=0, then 3 xor 0=3, 3+0=3.）

Sample Input 2

1422

Sample Output 2

52277

Sample Input 3

1000000000000000000

Sample Output 3

787014179

題意：給出一個整數 n，已知 0<=u,v<=n，求滿足 a xor b=u 且 a+b=v 的 a、b 對數

思路：

首先打表，可以發現前幾項有：1、2、4、5、8、10、13、14、18、21、26、28、33、36、40、41、46、50、57、60、68

可以發現：

是以直接用數組記錄前面已有的項目，再開一個 map 用于記憶化搜尋，然後遞歸即可

Source Program

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 1000000+5;
const int dx[] = {0,0,-1,1,-1,-1,1,1};
const int dy[] = {-1,1,0,0,-1,1,-1,1};
using namespace std;

LL a[25]={1,2,4,5,8,10,13,14,18,21,26,28,33,36,40,41,46,50,57,60,68};
map<LL,LL> mp;
LL cal(LL x) {
    if(x<=20)
        return a[x];
    if(mp[x])
        return mp[x];
    if(x%2)
        return mp[x]=(2*cal(x/2)%MOD+cal(x/2-1)%MOD)%MOD;
    else
        return mp[x]=(2*cal(x/2-1)%MOD+cal(x/2)%MOD)%MOD;
}
int main() {
    LL n;
    scanf("%lld",&n);
    printf("%lld\n",cal(n));
    return 0;
}