C++14(g++5.4) 解法, 执行用时: 190ms, 内存消耗: 3192K, 提交时间: 2018-07-31 00:09:22

#include<bits/stdc++.h>
using namespace std;
const int P=1e9+7;
long long n,m,dp[64][3][128],a[64],T;
long long dfs(int len,bool f,int pre,int sum){
	if(dp[len][pre][sum]!=-1&&!f) return dp[len][pre][sum];
	long long cnt=0;
	if(!len) return abs(sum-64);
	int lim=f?a[len]:1;
	for(int i=0;i<=lim;++i) {
		if(pre==2){
			if(i) cnt+=dfs(len-1,f&&i==a[len],i,sum);
			else cnt+=dfs(len-1,f&&i==a[len],pre,sum);
		}
		else{
			cnt+=dfs(len-1,f&&i==a[len],i,sum+(i==pre?1:-1));
		}
	}
	cnt%=P;
	return f?cnt:dp[len][pre][sum]=cnt;
}
long long div(long long tmp){
	int p=0;
	while(tmp) a[++p]=tmp%2,tmp>>=1;
	return dfs(p,1,2,64);
}
int main(){
	memset(dp,-1,sizeof(dp));
	for(scanf("%lld",&T);T--;){
		scanf("%lld",&n);
		printf("%lld\n",div(n));
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 90ms, 内存消耗: 1500K, 提交时间: 2020-02-28 13:41:11

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=150,_0=74,mod=1e9+7;
int C[N][N],ans[N][N],T,d[N],t;
LL n;
int main()
{
	for(int i=0;i<N;i++)
	C[i][0]=1;
	for(int i=1;i<N;i++)
	for(int j=1;j<=i;j++)
	C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	for(int i=-64;i<=64;i++)
	for(int j=0;j<=64;j++)
	for(int k=0;k<=j;k++)
	ans[i+_0][j]=(1LL*C[j][k]*abs(i+2*k-j)+ans[i+_0][j])%mod;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld",&n);
		for(t=0;n;d[++t]=n&1,n>>=1);
		int res=0,tot=0;
		for(int i=t-1;i>=1;i--)
		{
			int k=(d[i]==d[i+1])?1:-1;
			res=(res+ans[0+_0][i-1])%mod;
			if(d[i]==1)
			res=(res+ans[tot-k+_0][i-1])%mod;
			tot+=k;
		}
		printf("%d\n",(res+abs(tot))%mod);
		
		
	}
	return 0;
}