BZOJ 3329 xorequ

题面

不是权限题美滋滋。

由\(x\ xor\ 3x=2x\)得\(x\ xor\ 2x=3x\)

得\(x\ and\ 2x + x + 2x =3x\)

所以\(x\ and\ 2x=0\)

首先我们考虑\(f0[x]\)表示有x位二进制数（无限制），其中第x位填0的方案数，（位从1开始到第x位）

\(f1[x]\)表示有x位二进制数（无限制），其中第x位填1的方案数，

所以\(f0[x]=f0[x-1]+f1[x-1]\)，\(f1[x]=f0[x-1]\)

对于第一问，我们就可以数位DP了。

对于第二问，我们可以通过矩阵乘法优化DP。

注意考虑边界情况：

1. 不要忘记去掉0的情况。
2. 不要忘记n是否可以（\(2^n\)一定可以，\(n\)不一定）

/*
Author: CNYALI_LK
LANG: C++
PROG: 3329.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
    ll s=0,base=1;
    char c;
    while(!isdigit(c=getchar()))if(c=='-')base=-base;
    while(isdigit(c)){s=s*10+(c^48);c=getchar();}
    return s*base;
}
char WritellBuffer[1024];
template<class T>void write(T a,char end){
    ll cnt=0,fu=1;
    if(a<0){putchar('-');fu=-1;}
    do{WritellBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
    while(cnt){putchar(WritellBuffer[cnt]);--cnt;}
    putchar(end);
}
const ll p=1000000007;
void Add(ll &a,ll b){
    a-=((a+=b)>=p?p:0);
}
struct matrix{
    ll a[3][3];
    ll *operator [](ll n){return a[n];}
    matrix operator *(matrix b){
        matrix c;
        for(ll i=1;i<=2;++i)
            for(ll j=1;j<=2;++j){
                c[i][j]=0;
                for(ll k=1;k<=2;++k)Add(c[i][j],a[i][k]*b[k][j]%p);
        }
        return c;
    }
};
matrix operator ^ (matrix a,ll b){
    matrix c;
    c[1][1]=c[2][2]=1;
    c[1][2]=c[2][1]=0;
    while(b){
        if(b&1)c=c*a;
        a=a*a;
        b>>=1;
    }
    return c;
}
ll f0[88],f1[88];
matrix a,b;
int main(){
#ifdef cnyali_lk
    freopen("3329.in","r",stdin);
    freopen("3329.out","w",stdout);
#endif
    ll t,n;
    t=read();
    while(t){
        n=read();
        f0[1]=f1[1]=1;
        for(ll i=2;i<=64;++i){
            f0[i]=f1[i-1]+f0[i-1];
            f1[i]=f0[i-1];
        }
        ll ans=0;
        for(ll i=63;i;--i){
            if((1LL<<(i-1))&n){
                ans+=f0[i];
                if((1LL<<i)&n){
                    --ans;
                    break;
                }
            }
        }
        printf("%lld\n",ans);
        b[1][1]=1;b[2][1]=1;
        a[1][1]=a[1][2]=a[2][1]=1;
        b=(a^(n-1))*b;
        printf("%lld\n",(b[1][1]+b[2][1])%p);
        --t;
    }
    return 0;
}