题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3329


解法：x xor 2x=3x(与x xor 3x=2x等价)求满足等式且小于n的x的个数，与满足等式小于2n的数的个数。因为异或是不

进位的二进制加法，那么因为结果正好和加法相同，那么说明x在二进制上没有相邻的1。那么简单的数位DP就可以求出

满足这个的答案了。  在第一问的基础上打表可以发现答案恰好就是fib数列的第2项，所以我们矩阵快速幂搞一下。

///BZOJ 3329

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
LL dp[100][2];
LL n, digit[100];
LL dfs(int pos, int val, int jud){
    if(pos==0) return 1;
    if(!jud&&dp[pos][val]!=-1) return dp[pos][val];
    int up=jud?digit[pos]:1;
    LL ans=0;
    for(int i=0; i<=up; i++){
        if(!val||!i){
            ans += dfs(pos-1,i,jud&&i==up);
        }
    }
    if(!jud) dp[pos][val]=ans;
    return ans;
}
LL f(LL x){
    int pos=0;
    while(x){
        digit[++pos]=x&1;
        x/=2;
    }
    return dfs(pos,0,1);
}
struct Matrix{
    LL a[2][2];
    void init(){
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                a[i][j]=0;
            }
        }
    }
};
Matrix operator *(Matrix a, Matrix b){
    Matrix res;
    res.init();
    for(int i=0; i<2; i++){
        for(int j=0; j<2; j++){
            for(int k=0; k<2; k++){
                res.a[i][j]=(res.a[i][j]+a.a[i][k]*b.a[k][j])%mod ;
            }
        }
    }
    return res;
}
Matrix powmod(Matrix a, LL n){
    Matrix res;
    res.init();
    for(int i=0; i<2; i++) res.a[i][i]=1;
    while(n){
        if(n&1LL) res=res*a;
        a=a*a;
        n>>=1LL;
    }
    return res;
}
int main(){
    memset(dp, -1, sizeof(dp));
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%lld", &n);
        LL ans1 = f(n)-1;
        Matrix A, B;
        A.a[0][0]=A.a[0][1]=A.a[1][0]=1;A.a[1][1]=0;
        B.a[0][0]=1;B.a[1][0]=0;
        A=powmod(A,n+1);
        A=A*B;
        LL ans2=A.a[0][0];
        printf("%lld\n%lld\n", ans1, ans2);
    }
    return 0;
}