BZOJ 3329. Xorequ

传送门

看到方程感觉比较奇怪，变一下：

注意到 $3x=(x<<1)+x$

那么 $x \text{ xor } ((x<<1)+x)=(x<<1) $

左右同时异或 $x$ ，得到 $(x<<1)+x=(x<<1) \text{ xor } x$

因为 $\text{xor}$ 是不进位的加法

发现当且仅当 $(x<<1)$ 和 $x$ 二进制下同一位不存在都是 $1$ 的情况上式才成立

所以就是求二进制下没有相邻的 $1$ 的数的个数，显然是可以 $dp$ 的

首先设 $f[i][0/1]$ 表示前 $i$ 位，第 $i$ 位为 $0/1$ 时合法的方案数（此时没考虑 $n$ 的限制）

然后对 $n$ 数位 $dp$ ，求出第 $1$ 问

对于第二问直接对 $f$ 矩阵加速即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
    return x*f;
}
const int mo=1e9+7;
ll T,n,ans1;
ll f[107][2];
void dfs(int p)
{
    if(p<0) { ans1++; return; }
    if(n&(1ll<<p))
    {
        ans1+=f[p][0];
        if(p<62 && (n&(1ll<<p+1)) ) return;
        dfs(p-1);
    }
    else dfs(p-1);
}
inline int fk(int x) { return x>=mo ? x-mo : x; }
struct Matrix {
    int a[2][2];
    Matrix () { memset(a,0,sizeof(a)); }
    inline Matrix operator * (const Matrix &tmp) const {
        Matrix res;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                res.a[i][j]=fk(1ll*a[i][0]*tmp.a[0][j]%mo+1ll*a[i][1]*tmp.a[1][j]%mo);
        return res;
    }
}Ans,F;
inline Matrix ksm(Matrix x,ll y)
{
    Matrix res; res.a[0][0]=res.a[1][1]=1;
    while(y)
    {
        if(y&1) res=res*x;
        x=x*x; y>>=1;
    }
    return res;
}
int main()
{
    T=read();
    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];
    while(T--)
    {
        n=read(); dfs(62);
        Ans.a[0][0]=Ans.a[0][1]=1;
        F.a[0][0]=F.a[0][1]=1; F.a[1][0]=1;
        Ans=Ans*ksm(F,n);
        printf("%lld\n%d\n",ans1-1,Ans.a[0][0]);
        ans1=0;
    }
    return 0;
}