Xorequ 数位dp+矩阵快速幂

题目描述

给定正整数$n$，现有如下方程：x$igoplus$3x=2x，其中$igoplus$表示按位异或。

任务如下：

求出小于等于$n$的正整数中，有多少个数是该方程的解。
求出小于等于$2^n$的正整数中，有多少个数是方程的解，模$10^9+7$

输入格式

第一行一个正整数，表示$T$组数据。

接下来$T$行，每行一个正整数$N$。

输出格式

输出$2×T$行

第$2*i-1$行表示第$i$个数据中问题一的解

第$2*i$行表示第$i$个数据中问题二的解。

样例输入

1
1

样例输出

1
2

样例解释

$x=1与x=2$都是原方程的根，注意第一个问题的解不要$mod10^9+7$

$1leq Nleq10^{18},1leq Tleq1000$

问题一应该算是数位dp比较简单的题了

先来推一下性质$xigoplus2x=3x$，按位异或的话要优先考虑二进制的转移：

　　$2x$就是$x$向左移一位，$xigoplus2x$如果二进制中有重复位为1的话，那么异或得到的数只会比$3x$更小，$3x$可看作$x+2x$的不进位加法（其实这也是异或本身的性质）

所以$x$的寻找就是要找到小于等于$n$的正整数中二进制位没有连续1的数，方案数加和

开的数组真的好小qwq

问题二：$10^{18}$的话肯定就不能按位枚举了，因为要枚举$10^{18}-1$位，就算是O(n)的复杂度也不够，所以要考虑O($log^n$)的

　　在问题一中之所以要按位枚举，是因为给的数转移成二进制每一位都会存在限制，而问题二的2的几次方的二进制就是10000……

　　减一的话，由$n$位变成了$n-1$位，但是每一位都变成了1，111111……

　　从最高位开始就不会存在限制，就算每一位都选1也可以。

再来看一下如何求解，每一位上的数是0或1，手画一下可以发现一个递推的关系：

　　（$i$表示位数，$cnt$表示当前满足条件的方案数）

　　$i=1$时，$cnt=2$（1，0

　　$i=2$时，$cnt=3$（10，01，00

　　$i=3$时，$cnt=5$（101，100，010，001，000

　　$i=4$时，$cnt=8$（1010，1001，1000，0101，0100，0010，0001，0000

　　$i=5$时，$cnt=13$（10101，10100，10010，10001，10000，01010，01001，01000，00101，00100，00010，00001，00000

所以，这是一个菲波那契数列，用矩阵快速幂O($log^n$)求一下就可以了

还有一个小细节，就是，由$n$位变成了$n-1$位时，减1之前是100000……，因为只有一个1，所以这个数一定是满足条件的，方案数可以++

但是要求的$x$是正整数，所以应该减去没有任何1但不是正整数的0，方案数--

所以求问题二的时候，可以抵消，但是dfs求方案一的时候就需要减去0的那个一种方案

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;
int T,a[62];
ll n,dp[62][2];
ll dfs(int cnt,int flag,int k) {
    if(!cnt) return 1;
    if(!flag&&~dp[cnt][k]) return dp[cnt][k];
    ll res=0;
    int Max=flag?a[cnt]:1;
    for(int i=0;i<=Max;i++) {
        if(i) {
            if(!k) res+=dfs(cnt-1,flag&&(i==Max),1);
        }
        else res+=dfs(cnt-1,flag&&(i==Max),0);
    }
    if(!flag) return dp[cnt][k]=res;
    return res;
}
ll query(ll x) {
    int cnt=0;
    ll res=0;
    memset(dp,-1,sizeof(dp));
    memset(a,0,sizeof(a));
    while(x) {
        a[++cnt]=x&1;
        x>>=1;
    }
    for(int i=0;i<=a[cnt];i++) {
        res+=dfs(cnt-1,(i==a[cnt]),(i==1));
    }
    return res;
}
struct Matrix{
    ll mat[2][2];
    Matrix() {}
    Matrix operator*(Matrix const &b) const {
        Matrix res;
        memset(res.mat,0,sizeof(res.mat));
        for(int i=0;i<2;i++) {
            for(int j=0;j<2;j++) {
                for(int k=0;k<2;k++) {
                    res.mat[i][j]=(res.mat[i][j]+mat[i][k]*b.mat[k][j])%mod;
                }
            }
        }
        return res;
    }
};
Matrix pow_mod(Matrix base,ll n) {
    Matrix res;
    memset(res.mat,0,sizeof(res.mat));
    for(int i=0;i<2;i++) res.mat[i][i]=1;
    while(n) {
        if(n&1) res=res*base;
        base=base*base;
        n>>=1;
    }
    return res;
}
int main() {
    scanf("%d",&T);
    Matrix base;
    for(int i=0;i<2;i++) {
        for(int j=0;j<2;j++) {
            base.mat[i][j]=1;
        }
    }
    base.mat[1][1]=0;
    while(T--) {
        scanf("%lld",&n);
        printf("%lld
",query(n)-1);
        Matrix ans=pow_mod(base,n+2);
        printf("%lld
",ans.mat[0][1]);
    }
    return 0;
}