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

題意：給出一個(gè)整數(shù) n，已知 0<=u,v<=n，求滿足 a xor b=u 且 a+b=v 的 a、b 對(duì)數(shù)

思路：

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

可以發(fā)現(xiàn)：

因此直接用數(shù)組記錄前面已有的項(xiàng)目，再開一個(gè) 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;elsereturn 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; }

?

總結(jié)

以上是生活随笔為你收集整理的Xor Sum（AtCoder-2272）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。