Solution
发现 $x \ xor \ 2x = 3x$ 仅当 $x$ 的二进制中没有相邻的 $1$
对于第一个问题就可以进行数位DP 了。
但是对于第二个问题， 我们只能通过递推 打表 来算出答案了。
推公式 打表 可知， 这是一个斐波那契数列， $a_0 = 1, a_1 = 2, a_2 = 3$....
通过矩阵快速幂优化递推就可以过啦
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rd read()
#define ll long long
using namespace std; const int mod = 1e9 + ; const int N = ; int T, a[];
ll sum[N][], n; struct matrix {
ll s[][];
matrix operator * (const matrix &b) const {
matrix re;
memset(re.s, , sizeof(re.s));
for(int i = ; i <= ; ++i)
for(int k = ; k <= ; ++k)
for(int j = ; j <= ; ++j)
re.s[i][j] = (re.s[i][j] + s[i][k] * b.s[k][j]) % mod;
return re;
}
}ans, st; struct node {
int id;
ll in, out1, out2;
}b[]; ll read() {
ll X = , p = ; char c = getchar();
for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;
for(; c >= '' && c <= ''; c = getchar()) X = X * + c - '';
return X * p;
} ll dfs(int pos, int pre, int lim, int lead) {
if(!pos) return lead == ;
if(!lim && !lead && sum[pos][pre] != -)
return sum[pos][pre];
int up = lim ? a[pos] : ;
ll tmp = ;
for(int i = ; i <= up; ++i) {
if(pre && i)
continue;
tmp += dfs(pos - , i, lim && a[pos] == i, lead && i == );
}
if(!lim && !lead)
sum[pos][pre] = tmp;
return tmp;
} ll work(ll x) {
int len = ;
while(x) a[++len] = x % , x /= ;
return dfs(len , , true, true);
} inline bool cmp1(const node &A, const node &B ) {
return A.in < B.in;
} inline bool cmp2(const node &A, const node &B) {
return A.id < B.id;
} void print(ll x) {
sort(b + , b + + T, cmp1);
memset(sum, -, sizeof(sum));
memset(st.s, , sizeof(st.s));
memset(ans.s, , sizeof(ans.s));
st.s[][] = st.s[][] = st.s[][] = ;
ans.s[][] = ;
ans.s[][] = ;
printf("%lld\n", work(x));
for(; x; x >>= , st = st * st)
if(x & ) ans = ans * st;
printf("%lld\n", (ans.s[][] % mod + mod) % mod);
} int main()
{
T = rd;
for(; T; T--) print(rd);
}