BZOJ-3329: Xorequ

Description

x^3x=2x => x^2x=3x => x^2x=x+2x
亦或相当于对于每位进行模2的加法。那么原题意可化为：求解的个数，使得该数每位进行模2加法的答案等于不取模算的答案。将数二进制分解，发现当且仅当有两个连续的1时该解不合法。
数位DP即可。对于第二种n比较大的情况矩乘优化即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;//2^60>10^18
typedef long long ll;
ll n,f[70],g[70];//f:i位01串合法且首位为1 g:为0
const ll mod=1000000007;
void initialize()
{
    g[0]=1; f[1]=1; g[1]=1;
    for(int i=2;i<=60;++i)
        f[i]=g[i-1],g[i]=f[i-1]+g[i-1];
}
ll getans1(ll x)
{
    ++x; ll re=0;
    for(int i=60;i>=0;--i) if((x>>i)&1)
    {
        re+=f[i]+g[i];
        if((x>>(i+1))&1) break;
    }
    return re;
}
struct matrix1
{
    ll a[2][2];
    matrix1(){memset(a,0,sizeof a);}
    matrix1 operator *(const matrix1 z)
    {
        matrix1 re;
        re.a[0][0]=(a[0][0]*z.a[0][0]+a[0][1]*z.a[1][0])%mod;
        re.a[0][1]=(a[0][0]*z.a[0][1]+a[0][1]*z.a[1][1])%mod;
        re.a[1][0]=(a[1][0]*z.a[0][0]+a[1][1]*z.a[1][0])%mod;
        re.a[1][1]=(a[1][0]*z.a[0][1]+a[1][1]*z.a[1][1])%mod;
        return re;
    }
};
struct matrix2
{
    ll a[2];
    matrix2(){memset(a,0,sizeof a);}
    matrix2 operator *(const matrix1 z)
    {
        matrix2 re;
        re.a[0]=(a[0]*z.a[0][0]+a[1]*z.a[1][0])%mod;
        re.a[1]=(a[0]*z.a[0][1]+a[1]*z.a[1][1])%mod;
        return re;
    }
};
ll getans2(ll x)
{
    matrix2 re;
    re.a[0]=0; re.a[1]=1;
    matrix1 I;
    I.a[0][0]=0; I.a[0][1]=1;
    I.a[1][0]=1; I.a[1][1]=1;
    while(x)
    {
        if(x&1) re=re*I;
        I=I*I; x>>=1;
    }
    return (re.a[0]+re.a[1])%mod;
}
int main()
{
    initialize(); int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%lld",&n);
        printf("%lld\n%lld\n",getans1(n)-1,getans2(n));
    }
    return 0;
}