记录编号	140100	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[CF 388D]Fox的完美集合	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2014-11-19 15:18:10	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
LL MOD=1000000007;
LL quickpow(LL a,LL n){
	LL ans=1;
	while(n){
		if(n&1) ans=(ans*a)%MOD;
		a=(a*a)%MOD;
		n>>=1;
	}
	return ans;
}
const int SIZE=35;
int N;
LL f[SIZE][SIZE]={0},g[SIZE][SIZE]={0};
//f[i][j]:确定到i位,有j个基,小于N,g是等于N
void add(LL &x,LL y){
	y%=MOD;
	x+=y,x%=MOD;
}
void work(void){
	g[32][0]=1;//这一位总是0
	for(int i=31;i>=0;i--){
		for(int j=0;j<=31;j++){
			//f的第一种来源:之前已分出大小,这一位加一个基
			if(j>0) add(f[i][j],f[i+1][j-1]);
			//f的第二种来源:之前已分出大小,这一位不加基,已有的基这一位随便搞
			add(f[i][j],f[i+1][j]*quickpow(2,j));
			if((N>>i)&1){//f的第三种来源:之前未分出大小,通过设置已有基的这一位让它恒小于N
				/*将基写成矩阵后,我们规定主元所在列只能有这一个1,因此更高位与N相同的表示必须用上所有基,
				故有2^(j-1)种方法让这一位是0,特别地j=0时有一种方法*/
				add(f[i][j],g[i+1][j]*quickpow(2,max(j-1,0)));
			}
			if((N>>i)&1){//N的这一位是1
				//g的第一种来源:之前未分出大小,这一位加基
				if(j>0) add(g[i][j],g[i+1][j-1]);
				//g的第二种来源:之前未分出大小,这一位不加基,通过设置已有基的这一位让它等于N
				//根据求f时的分析,有2^(j-1)种方法,特别地当j=0时有0种
				if(j>0) add(g[i][j],g[i+1][j]*quickpow(2,j-1));
			}
			else{//N的这一位是1
				//g的唯一一种来源:之前未分出大小,这一位不加基,通过设置已有基让它为0
				//有2^(j-1)种,特别地j=0时有一种
				add(g[i][j],g[i+1][j]*quickpow(2,max(j-1,0)));
			}
		}
	}
	LL ans=0;
	for(int i=0;i<=31;i++) add(ans,f[0][i]+g[0][i]);
	cout<<ans<<endl;
}
int main(){
	freopen("foxandperfectsets.in","r",stdin);
	freopen("foxandperfectsets.out","w",stdout);
	cin>>N;
	work();
	return 0;
}