题目概述

求 $[1,n]$ 中满足 $x\ xor\ 3x=2x$ 的 $x$ 的个数以及 $[1,2^n]$ 中 $x$ 的个数。

解题报告

我竟然分析成了 $x=3x\ xor\ 2x$ ，然后毫无头绪……你看这式子多像 $x+2x=3x$ 啊，再加上异或可以理解为不进位的二进制加法，所以应该分析成这样 $x\ xor\ 2x=3x$ 。不过都试一遍也没什么关系对吧。

那么想要满足 $x\ xor\ 2x=x+2x$ ，也就意味着 $x$ 二进制任意一位不能和后一位同时为 $1$ 。

然后就可以瞎搞了，$f[i][0/1]$ 表示第 $i$ 位为 $0/1$ 时的方案数，很显然：

$$ f[i][0]=f[i-1][0]+f[i-1][1],f[i][1]=f[i-1][0] $$

第一问数位DP，第二问直接矩阵快速幂优化一下就行了。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=60,MOD=1e9+7;

int te,a[maxn+5];LL n,f[maxn+5][2];
struct Matrix{
    int r,c,s[2][2];
    inline void zero(int R,int C) {r=R;c=C;for (int i=0;i<r;i++) for (int j=0;j<c;j++) s[i][j]=0;}
    inline void unit(int R) {zero(R,R);for (int i=0;i<r;i++) s[i][i]=1;}
};
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline Matrix operator * (const Matrix &a,const Matrix &b){
    static Matrix c;c.zero(a.r,b.c);
    for (int i=0;i<a.r;i++)
        for (int j=0;j<b.c;j++)
            for (int k=0;k<a.c;k++)
                AMOD(c.s[i][j],(LL)a.s[i][k]*b.s[k][j]%MOD);
    return c;
}
Matrix ans,T;

LL Dfs(int st,int j,bool fl){
    if (!st) return 1;if (!fl&&~f[st][j]) return f[st][j];LL ans=Dfs(st-1,0,fl&&!a[st]);
    if (!j&&(!fl||a[st])) ans+=Dfs(st-1,1,fl);if (!fl) f[st][j]=ans;return ans;
}
inline Matrix Pow(Matrix w,LL b) {Matrix s;s.unit(w.r);for (;b;b>>=1,w=w*w) if (b&1) s=s*w;return s;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    T.zero(2,2);T.s[0][0]=T.s[0][1]=T.s[1][0]=1;T.s[1][1]=0;
    for (memset(f,255,sizeof(f)),scanf("%d",&te);te;te--){
        scanf("%lld",&n);LL x=n;a[0]=0;do a[++a[0]]=x&1,x>>=1; while (x);
        printf("%lld\n",Dfs(a[0],0,true)-1);ans.zero(1,2);ans.s[0][0]=1;ans.s[0][1]=1;
        ans=ans*Pow(T,n-1);printf("%d\n",(ans.s[0][0]+ans.s[0][1])%MOD);
    }
    return 0;
}