首页 > 代码库 > Bitwise And Queries

Bitwise And Queries

2024-08-13 14:39:16   223人阅读

Bitwise And Queries

Time limit: 1500 ms
Memory limit: 128 MB

You are given QQ queries of the form a\ b\ xa b x. Count the number of values yy such that a \leq y \leq ba≤y≤b and x\ \& \ y = xx & y=x, where we denote by \&& the bitwise and operation.

Standard input

The first line contains a single integer QQ.

Each of the following QQ lines contains three integers a\ b\ xa b x, representing a query.

Standard output

Output QQ lines, each containing a single integer representing the answer to a query.

Constraints and notes

  • 1 \leq Q \leq 10^51≤Q≤10?5??
  • 1 \leq a \leq b \leq 10^{18}1≤a≤b≤10?18??
  • 0 \leq x \leq 10^{18}0≤x≤10?18??
InputOutput
41 10 35 10 01 63 732 100 32
26837
 

 

x&y==x,说明x二进制表示上，有1的地方，y也要有1，是0的地方，y可以是0或者1，记忆化瞎几把搜一下就行了，每次可以选择的有0或1，再判断一下能否取0或1。

lr表示此时这个位置y能否取任意数，只要前面x为0，y为1时，递归选0的话，就说明y后面的数可以任意取了，因为前面有1选了0，那后面无论选什么都不可能超过上界了。
技术分享
#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 200005;const int inf = 0x3f3f3f3f;const int mod = 1000000007;LL dp[65][2];int A[65],X[65];LL solve(int cur,int lr){    if(cur == 64)return 1;    if(dp[cur][lr] != -1)return dp[cur][lr];    if(lr){        if(A[cur]){            return dp[cur][lr] = solve(cur + 1,lr);        }        else {            return dp[cur][lr] = 2 * solve(cur + 1,lr);        }    }    else {        if(A[cur]){            if(X[cur])return dp[cur][lr] = solve(cur + 1,lr);            else return dp[cur][lr] = 0;        }        else {            if(X[cur])return dp[cur][lr] = solve(cur+1,1) + solve(cur+1,lr);            else return dp[cur][lr] = solve(cur+1,lr);        }    }}void print(int *x){    for(int i = 0; i < 64; i++)        printf("%d",x[i]);    puts("");}int main(){#ifdef local    freopen("in", "r", stdin);#endif    int T;    scanf("%d",&T);    while(T--){        LL x,y,a;        scanf("%lld%lld%lld",&x,&y,&a);        x--;        for(int i = 0; i < 64; i++){            A[i] = a & 1;            a >>= 1;        }        reverse(A,A+64);//        print(A);        for(int i = 0; i < 64; i++){            X[i] = x & 1;            x >>= 1;        }        reverse(X,X+64);//        print(X);        memset(dp,-1,sizeof dp);        LL res = solve(0,0);        for(int i = 0; i < 64; i++){            X[i] = y & 1;            y >>= 1;        }        reverse(X,X+64);//        print(X);        memset(dp,-1,sizeof dp);        res = solve(0,0) - res;        printf("%lld\n",res);    }}
View Code

 

Bitwise And Queries


联系
我们