题意
求区间内有多少数x满足x^4x^5x=0
1≤l≤r≤1018.
题解
根据异或的性质可以推到 x^4x=5x -->x^4x=x+4x
即x和4x每一位都不同,即x和(x<<2)每一位都不同,就是x中每一位1都与他前前一位不同。
那么就很简单了,可以很容易写出数位DP状态f[s][ppre][pre],不过前导零貌似会有影响,因为他本来无效,而只记录那两维的话就不知道是有效的还是无效的,所以很自然想到再开一维表示前两位有几个是有效的。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> using namespace std; #define ll long long int t; ll l,r; int len,num[70]; ll f[70][2][2][3];//最后一维表示有几个有效数字 ll dfs(int s,int ppre,int pre,int ok,bool lim){ if(!s) return 1; if(!lim&&f[s][ppre][pre][ok]!=-1) return f[s][ppre][pre][ok]; int mx=lim ? num[s] : 1 ; ll ret=0; for(int i=0;i<=mx;i++){ if(ok==2&&i&ppre) continue; ret+=dfs(s-1,pre,i,!ok&&!i ? ok : min(2,ok+1),lim&&i==mx); } if(!lim) f[s][ppre][pre][ok]=ret; return ret; } ll cx(ll x){ len=0; while(x){ num[++len]=x&1; x>>=1; } return dfs(len,0,0,0,true); } void nice(){ scanf("%lld%lld",&l,&r); printf("%lld ",cx(r)-cx(l-1)); } int main(){ memset(f,-1,sizeof(f)); scanf("%d",&t); while(t--) nice(); }