题目大意

给定一个数(n)，求选择(0 sim n)中任意个数的数字组成的集合(S)中，有多少满足若(ain S,bin S),则(a igoplus b in S),输出方案数对(1e9+7)取模。

题目分析

设(f[i][j][k])表示从第(i)位到最高位，已经选了(j)个基，且由基(igoplus)得到的最大值与(n)的差值是否在(2^i)以内的方案数。

况一：当(k=0)（异或最大值(+2^i<n)）时，考虑第(i-1)位。

如果该位要作为单独一个基，那么有(f[i-1][j+1][0]+=f[i][j][0])，

该位单独作基，则新增情况数为之前有的情况，视为在之前每种情况上(x)新增一个(2^{i-1} )的基，

由设可保证新构成的集合异或最大值与(n)的差值在(2^{i-1})之外，所以算在(f[i-1][j+1][0])中。

如果该位不单独作基，而是放入已经拥有的j个基中，

那么对于每个基，都有放与不放两种选择，共(2^j)种，(f[i-1][j][0]+=2^j*f[i][j][0])。

况二：当(k=1)（异或最大值(+2^i>=n)）时，考虑第(i-1)位。

讨论(n)在第(i-1)位是否为(1)：

1、(n)在第(i-1)位不为(1)，异或最大值(+2^{i-1}>n)：

此时最大值无法新增一个(2^{i-1})。

那么，我们只能继承令第(i-1)位为偶数个(1)的情况，因为只有这样，最大值才不会改变，共(2^{j-1})种。

2、(n)在第(i-1)位为(1)，异或最大值(+2^{i-1}≤n)：

如果在第(i-1)位取(0)，那么新得到的集合异或最大值(+2^{i-1}≤n)，因此应存入(f[i-1][j][0])中，共(2^{j-1})种。

如果在第(i-1)位取(1)，那么新得到的集合异或最大值(+2^{i-1}≥n)，因此应存入(f[i-1][?][1])中。

对于第(i-1)位单独作基的情况，可以有(f[i][j][1])种，存入(f[i-1][j+1][1])中,(f[i-1][j+1][1]+=f[i][j][1])。
对于第(i-1)位不单独作基的情况，可以对每个基选择放与不放，且必须放奇数个，共(2^{j-1})种选择，

因此(f[i-1][j][1]+=2^{j-1}*f[i][j][1])。

注意：

对于所有情况，当(j=0),对于选择第(i-1)位为(0)的情况，(2^{j-1})算作(1)；

对于选择第(i-1)位为(1)的情况，(2^{j-1})算作(0)，因为就算你没有选择一个基，你的异或和仍可以视作(0)。

代码实现

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#define MAXN 0x7fffffff
typedef long long LL;
const int mod=1e9+7;
using namespace std;
inline int Getint(){
	register int x=0,f=1;
	register char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int ans,f[35][35][2];
void Add(int &x,int y){x=((x+y>=mod)?(x+y-mod):(x+y));}
int main(){
	int n=Getint();
	f[30][0][1]=1;
	for(int i=30;i>0;i--)
		for(int j=0;j<=30;j++){
			Add(f[i-1][j][0],(1LL<<j)*f[i][j][0]%mod);
			Add(f[i-1][j+1][0],f[i][j][0]);
			int x=j?(1<<(j-1)):1,y=j?(1<<(j-1)):0;
			if(n>>(i-1)&1){
				Add(f[i-1][j][0],(LL)x*f[i][j][1]%mod);
				Add(f[i-1][j][1],(LL)y*f[i][j][1]%mod);
				Add(f[i-1][j+1][1],f[i][j][1]);
			}else Add(f[i-1][j][1],(LL)x*f[i][j][1]%mod);
		}
	for(int i=0;i<=30;i++)
		Add(ans,f[0][i][0]),Add(ans,f[0][i][1]);
	cout<<ans;
	return 0;
}