Description：

求小于等于 $n$ 和 $2^n$ 的正整数中，有多少是 $x\text{ xor }3x=2x$ 的解。

$1\le n\le 10^{18},1\le T \le 1000$

Solution：

移项，把 $3x$ 拆开，得 $(x+2x)=x\text{ xor }2x$ ，即 $(x+(x<<1))=x\text{ xor }(x<<1)$ ，也就是二进制下不含相邻一的数字的个数，二进制数位 $DP$ ，记 $f[i][0/1]$ 表示到了第 $i$ 位选 $0/1$ 的方案数，转移为 $f[i][0]=f[i-1][0]+f[i-1][1],f[i][1]=f[i-1][0]$ 。

然后从高到低枚举每一位，如果这一位是一，就加上 $f[i][0]$ ，注意原数中如果有连续相同的两位就 $break$ ，因为后面的都不合法。

然后对于第二问，打表发现是一个斐波那契数列，矩阵快速幂即可。原因是 $f[i][0]=f[i-1][0]+f[i-1][1]=f[i-1][0]+f[i-2][0]$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll n;

#define MAXL 70

ll f[MAXL][2];

#define MOD 1000000007

struct matrix

{

	ll m[3][3];

	matrix(){memset(m,0,sizeof(m));}

	friend matrix operator * (matrix a,matrix b)

	{

		matrix c;

		for(int i = 1;i <= 2;++i)

			for(int j = 1;j <= 2;++j)

				for(int k = 1;k <= 2;++k)

					c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j] % MOD) % MOD;

		return c;

	}

	friend matrix operator ^ (matrix a,ll b)

	{

		matrix res = a;--b;

		while(b > 0)

		{

			if(b & 1)res = res * a;

			a = a * a;

			b = b >> 1;

		}

		return res;

	}

}s;

void work()

{

	scanf("%lld",&n);

	memset(f,0,sizeof(f));

	f[0][0] = f[0][1] = 1;

	for(int i = 1;i <= 62;++i)

	{

		f[i][0] = f[i - 1][0] + f[i - 1][1];

		f[i][1] = f[i - 1][0];

	}

	ll ans = 0;

	for(ll i = 62;i >= 0;--i)

	{

		if((n & (1ll << i)))ans += f[i][0];

		if((n & (1ll << i)) && (n & (1ll << (i + 1))))

		{

			--ans;

			break;

		}

	}

	printf("%lld\n",ans);

	s.m[1][1] = s.m[1][2] = s.m[2][1] = 1;s.m[2][2] = 0; 

	s = s ^ (n + 1);

	printf("%lld\n",s.m[1][1]);

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}