C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 388K, 提交时间: 2020-01-23 11:24:46

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,g[65],mod=1000000007;
ll qpow(ll a,ll b,ll mod)
{
    ll ret=1;
    while (b)
    {
        if (b&1)ret=(ret*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ret;
}
ll f(ll x)
{
    switch(x%4)
    {
    case 0:return x;
    case 1:return 1;
    case 2:return x+1;
    case 3:return 0;
    }
}
ll h[2]={291172004,582344008};//2^(64-1)even,2^(65-1)odd
ll inv3=333333336;//inv(3,mod);
int main()
{
    for (int i=1; i<=64; ++i) //1010...
        g[i]=2*g[i-1]+(i&1);
    cin>>t;
    while (t--)
    {
        cin>>n;
        if (n<=62)cout<<(g[n]^f(n-1))%mod<<endl;
        else
        {
            ll ans=(g[62+(n&1)]^f(n-1))%mod;
            ll pow=h[n&1];
            ll m=(n-64)/2;
            m=(qpow(4,m+1,mod)-1)*inv3%mod;
            ans=(ans+pow*m)%mod;
            cout<<ans<<endl;
        }
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 492K, 提交时间: 2020-01-19 16:12:58

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MD=1e9+7;
ll quick_pow(ll x,ll y) {
	ll ans=1;
	while(y) {
		if(y&1) ans=ans*x%MD;
		y>>=1;
		x=x*x%MD;
	}
	return ans;
}
void add(ll &x,ll y) {
	x+=y;
	if(x>=MD) x-=MD;
	if(x<0) x+=MD;
}
int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		ll n,ans=0;
		scanf("%lld",&n);
		for(int i=0;i<n%4;i++) {
			ans^=(n-i-1);
		}
		if(n&1) {
			n--;
			for(int i=0;i<=min(n,1LL*60);i+=2) {
				ans^=1LL<<i;
			}
			ans%=MD;
			if(n>60) {
				ll x=quick_pow(2,62),y=quick_pow(4,(n-59)/2);
				add(y,-1);
				add(ans,1LL*x*y%MD*quick_pow(3,MD-2)%MD);
			}
		}
		else {
			n--;
			for(int i=1;i<=min(n,1LL*60);i+=2) {
				ans^=1LL<<i;
			}
			ans%=MD;
			if(n>60) {
				ll x=quick_pow(2,61),y=quick_pow(4,(n-59)/2);
				add(y,-1);
				add(ans,1LL*x*y%MD*quick_pow(3,MD-2)%MD);
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}