2019牛客多校7H

ACM › 刷题实战 › 牛客
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

###name
Pair

###descirption
Given three integers A, B, C. Count the number of pairs <x,y> (with
1≤x≤A and 1≤y≤B)such that at least one of the following is true:

  • (x and y) > C
  • (x xor y) < C
    (“and”, “xor” are bit operators)

###input
The first line of the input gives the number of test cases, T (T≤100). T test cases follow.

For each test case, the only line contains three integers A, B and C.
$1≤A,B,C≤10^9$

###output
For each test case, the only line contains an integer that is the number of pairs satisfying the condition given in the problem statement.

###sample input
3
3 4 2
4 5 2
7 8 5

###sample output
5
7
31

###toturial
可以直接dfs搜索，然后记忆化加速，写起来很复杂，但是能过

###code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
using namespace std;
 
typedef  long long ll;
 
typedef pair<pair<int,int>,pair<int,int>> pair4;
inline pair4 mp(int a,int b,int c,int d){return make_pair(make_pair(a,b),make_pair(c,d));}
 
map<pair4,ll> hashxor,hashand;
ll gxor(ll a,ll b,ll hi,ll c){//       ^<c
    if(a==-1||b==-1)return 0;
    if(hi<=1) {
        ll ct=0;
        for(ll i=0;i<=a;i++){
            for(ll j=0;j<=b;j++){
                if((i^j)<c) ct++;
            }
        }
        return ct;
    }
 
    if(hashxor.find(mp(a,b,hi,c))!=hashxor.end()) return hashxor[mp(a,b,hi,c)];
 
    ll a0=a>=hi-1?hi-1:a;// bg with 0
    ll b0=b>=hi-1?hi-1:b;// bg with 1
    ll a1=a>=hi?(a&(hi-1)):-1;
    ll b1=b>=hi?(b&(hi-1)):-1;
    if(c&hi) return hashxor[mp(a,b,hi,c)]=(a0+1)*(b0+1)+(a1+1)*(b1+1)+gxor(a0,b1,hi>>1,c&(hi-1))+gxor(a1,b0,hi>>1,c&(hi-1));
    else return hashxor[mp(a,b,hi,c)]=gxor(a0,b0,hi>>1,c&(hi-1))+gxor(a1,b1,hi>>1,c&(hi-1));
}
 
ll gand(ll a,ll b,ll hi,ll c){//  &>c
    if(a==-1||b==-1)return 0;
    if(hi<=1) {
        ll ct=0;
        for(ll i=0;i<=a;i++){
            for(ll j=0;j<=b;j++){
                if((i&j)>c) ct++;
            }
        }
        return ct;
    }
 
    if(hashand.find(mp(a,b,hi,c))!=hashand.end()) return hashand[mp(a,b,hi,c)];
 
    ll a0=a>=hi-1?hi-1:a;// bg with 0
    ll b0=b>=hi-1?hi-1:b;// bg with 1
    ll a1=a>=hi?(a&(hi-1)):-1;
    ll b1=b>=hi?(b&(hi-1)):-1;
    if(c&hi) return hashand[mp(a,b,hi,c)]=gand(a1,b1,hi>>1,c&(hi-1));
    else return hashand[mp(a,b,hi,c)]=(a1+1)*(b1+1)+gand(a0,b1,hi>>1,c&(hi-1))+gand(a1,b0,hi>>1,c&(hi-1))+gand(a0,b0,hi>>1,c&(hi-1));
}
 
ll f(ll a,ll b,ll hi,ll c){// &>c ^<c
    if(hi<=1){
        ll ct=0;
        for(ll i=0;i<=a;i++){
            for(ll j=0;j<=b;j++){
                if((i&j)>c||(i^j)<c) ct++;
            }
        }
        return ct;
    }
    ll a0=a>=hi-1?hi-1:a;// bg with 0
    ll b0=b>=hi-1?hi-1:b;// bg with 1
    ll a1=a>=hi?(a&(hi-1)):-1;
    ll b1=b>=hi?(b&(hi-1)):-1;
    if(c&hi) return (a0+1)*(b0+1)+(a1+1)*(b1+1)+gxor(a0,b1,hi>>1,c&(hi-1))+gxor(a1,b0,hi>>1,c&(hi-1));// ^ ^  & &
    else return (a1+1)*(b1+1)+gand(a0,b1,hi>>1,c&(hi-1))+gand(a1,b0,hi>>1,c&(hi-1))+f(a0,b0,hi>>1,c&(hi-1));
}
 
 
ll debug(ll a,ll b,ll c){
    hashxor.clear();
    hashand.clear();
 
    ll hi=max({a,b,c});
    while(hi&(hi-1)) hi&=hi-1;
    return f(a,b,hi,c)+1-min(a+1,c)-min(b+1,c);
}
 
ll baoli(ll a,ll b,ll c){
    ll ct=0;
    for(ll i=1;i<=a;i++){
        for(ll j=1;j<=b;j++){
            if((i&j)>c||(i^j)<c) ct++;
        }
    }
    return ct;
}
 
int main(){
//    srand(time(NULL));
//    int up=300;
//    while(true){
//        int i=rand()%20000+1;
//        int j=rand()%20000+1;
//        int k=rand()%20000+1;
//        int fuck1=baoli(i,j,k);
//        int fuck2=debug(i,j,k);
//        cout<<i<<" "<<j<<" "<<k<<" "<<" "<<fuck1<<" "<<fuck2<<endl;
//        if(fuck1!=fuck2){
//            cout<<baoli(i,j,k)<<endl;
//            cout<<debug(i,j,k)<<endl;
//            cout<<i<<j<<k<<endl;
//            getchar();
//        }
//
//
//    }
    ll a,b,c,t;
    scanf("%lld",&t);
    while(t--){
        hashxor.clear();
        hashand.clear();
 
        scanf("%lld%lld%lld",&a,&b,&c);
        ll hi=max({a,b,c});
        while(hi&(hi-1)) hi&=hi-1;
        printf("%lld\n",f(a,b,hi,c)+1-min(a+1,c)-min(b+1,c));
    }
}

###toturial2
考虑数位dp

###code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define REP(i,j,k) for(int i=(j);i<=(k);i++)
ll dp[33][2][2][3][3],A[33],B[33],C[33];

ll cmp(ll a,ll b){
    if(a<b) return -1;
    if(a==b) return 0;
    return 1;
}

ll dfs(ll bit,ll la,ll lb,ll ad,ll xr){
    if(bit==-1) return ad==1||xr==-1;
    ll&res=dp[bit][la][lb][ad+1][xr+1];
    if(res!=-1) return res;
    res=0;
    REP(i,0,la?A[bit]:1) REP(j,0,lb?B[bit]:1) res+=dfs(bit-1,la&&i==A[bit],lb&&j==B[bit],ad?ad:cmp(i&j,C[bit]),xr?xr:cmp(i^j,C[bit]));
    return res;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(dp,-1,sizeof(dp));
        ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c);
        REP(i,0,30) A[i]=bool(1<<i&a),B[i]=bool(1<<i&b),C[i]=bool(1<<i&c);
        printf("%lld\n",dfs(30,1,1,0,0)+1-min(a+1,c)-min(b+1,c));
    }
}