1<=N<=1018,1<=T<=1000
问题一应该算是数位dp比较简单的题了
先来推一下性质x^2x=3x，按位异或的话要优先考虑二进制的转移：
2x就是x向左移一位，x^2x如果二进制中有重复位为1的话，那么异或得到的数只会比3x更小，3x可看作x+2x的不进位加法（其实这也是异或本身的性质）
所以x的寻找就是要找到小于等于n的正整数中二进制位没有连续1的数，方案数加和
开的数组真的好小qwq
问题二：2的1e18次方的话肯定就不能按位枚举了，因为要枚举（1e18-1）位，就算是O(n)的复杂度也不够，所以要考虑O(logn)的
在问题一中之所以要按位枚举，是因为给的数转移成二进制每一位都会存在限制，而问题二的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(logn)求一下就可以了
还有一个小细节，就是，由n位变成了（n-1）位时，减1之前是100000……，因为只有一个1，所以这个数一定是满足条件的，方案数可以++
但是要求的x是正整数，所以应该减去没有任何1但不是正整数的0，方案数--
所以求问题二的时候，可以抵消，但是dfs求方案一的时候就需要减去0的那个一种方案
1 #include <bits/stdc++.h> 2 #define mod 1000000007 3 using namespace std; 4 typedef long long ll; 5 int T,a[62]; 6 ll n,dp[62][2]; 7 ll dfs(int cnt,int flag,int k) { 8 if(!cnt) return 1; 9 if(!flag&&~dp[cnt][k]) return dp[cnt][k]; 10 ll res=0; 11 int Max=flag?a[cnt]:1; 12 for(int i=0;i<=Max;i++) { 13 if(i) { 14 if(!k) res+=dfs(cnt-1,flag&&(i==Max),1); 15 } 16 else res+=dfs(cnt-1,flag&&(i==Max),0); 17 } 18 if(!flag) return dp[cnt][k]=res; 19 return res; 20 } 21 ll query(ll x) { 22 int cnt=0; 23 ll res=0; 24 memset(dp,-1,sizeof(dp)); 25 memset(a,0,sizeof(a)); 26 while(x) { 27 a[++cnt]=x&1; 28 x>>=1; 29 } 30 for(int i=0;i<=a[cnt];i++) { 31 res+=dfs(cnt-1,(i==a[cnt]),(i==1)); 32 } 33 return res; 34 } 35 struct Matrix{ 36 ll mat[2][2]; 37 Matrix() {} 38 Matrix operator*(Matrix const &b) const { 39 Matrix res; 40 memset(res.mat,0,sizeof(res.mat)); 41 for(int i=0;i<2;i++) { 42 for(int j=0;j<2;j++) { 43 for(int k=0;k<2;k++) { 44 res.mat[i][j]=(res.mat[i][j]+mat[i][k]*b.mat[k][j])%mod; 45 } 46 } 47 } 48 return res; 49 } 50 }; 51 Matrix pow_mod(Matrix base,ll n) { 52 Matrix res; 53 memset(res.mat,0,sizeof(res.mat)); 54 for(int i=0;i<2;i++) res.mat[i][i]=1; 55 while(n) { 56 if(n&1) res=res*base; 57 base=base*base; 58 n>>=1; 59 } 60 return res; 61 } 62 int main() { 63 scanf("%d",&T); 64 Matrix base; 65 for(int i=0;i<2;i++) { 66 for(int j=0;j<2;j++) { 67 base.mat[i][j]=1; 68 } 69 } 70 base.mat[1][1]=0; 71 while(T--) { 72 scanf("%lld",&n); 73 printf("%lld\n",query(n)-1); 74 Matrix ans=pow_mod(base,n+2); 75 printf("%lld\n",ans.mat[0][1]); 76 } 77 return 0; 78 }
原文：https://www.cnblogs.com/1999-09-21Karry-erfs/p/13466608.html