2020 CCPC网络赛 - 1012 Xor

题意:

求 满 足 x ∈ [ 0 , A ] , y ∈ [ 0 , B ] , ∣ x − y ∣ ≤ K , x   X O R   y ≤ W 的 ( x , y ) 的 对 数 求满足x \in [0,A],y \in [0,B],|x-y| \leq K,x \ XOR \ y \leq W 的(x,y)的对数 求满足x∈[0,A],y∈[0,B],∣x−y∣≤K,x XOR y≤W的(x,y)的对数

Solution:

∣ x − y ∣ ≤ K ⇒   x − y ≤ K   a n d   y − x ≤ K   ⇒   y − x + K ≥ 0   a n d   x − y + K ≥ 0 |x-y| \leq K \Rightarrow \ x-y\leq K \ and \ y-x \leq K \ \Rightarrow \ y-x+K \geq 0 \ and \ x-y+K \geq 0 ∣x−y∣≤K⇒ x−y≤K and y−x≤K ⇒ y−x+K≥0 and x−y+K≥0
我们可以在 D F S DFS DFS中记录当前 ( y − x + K ) / ( x − y + K ) (y-x+K) /(x-y+K) (y−x+K)/(x−y+K) 的值,但由于两个式子的取值范围很大,我们不能直接进行 D P DP DP
对 于 每 一 位 我 们 存 在 的 转 移 为 : { b e f y − x + K ∗ 2 + ( b i t y − b i t x ) + b i t K b e f x − y + K ∗ 2 + ( b i t x − b i t y ) + b i t K 对于每一位我们存在的转移为:\\ \left\{\begin{matrix} bef_{y-x+K}*2+(bit_y - bit_x) +bit_K& \text{}\\ bef_{x-y+K}*2+(bit_x - bit_y) +bit_K& \text{}\\ \end{matrix}\right. 对于每一位我们存在的转移为:{befy−x+K​∗2+(bity​−bitx​)+bitK​befx−y+K​∗2+(bitx​−bity​)+bitK​​​
.
发现 ( b i t x − b i t y ) + b i t K   ∈ [ − 1 , 2 ] (bit_x - bit_y) + bit_K \ \in[-1,2] (bitx​−bity​)+bitK​ ∈[−1,2],那显然如果 b e f < − 2    , bef < -2 \ \ , bef<−2  , b e f ∗ 2 + ( b i t x − b i t y ) + b i t K < 0 bef*2 +(bit_x - bit_y) + bit_K < 0 bef∗2+(bitx​−bity​)+bitK​<0是恒成立的,如果 b e f ≥ 1 bef \geq 1 bef≥1,上述式子大于等于 0 0 0恒成立.
故式子的取值只有 0 , 大 于 0 , − 1 , 小 于 − 1 0,大于0,-1,小于-1 0,大于0,−1,小于−1四种情况,此时我们直接数位DP即可

Code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <map>
#include <string>
#include <cstring>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
const int maxn = 1e5+7;

int A,B,K,W;
ll dp[63][3][3][2][2][2];
int vis[63][3][3][2][2][2];
ll bit[63];

int getbool(bool x) {
    return x? 1:0;
}

int getbit(int x,int y) {
    return (x&y)? 1:0;
}

ll dfs(int wei,int c1,int c2,bool lim1,bool lim2,bool lim3) {
    if(vis[wei][c1+1][c2+1][getbool(lim1)][getbool(lim2)][getbool(lim3)]) return dp[wei][c1+1][c2+1][getbool(lim1)][getbool(lim2)][getbool(lim3)];
    if(wei == -1) {
        return c1 >= 0 && c2 >= 0? 1:0;
    }
    int lt1 = lim1? getbit(bit[wei],A):1;
    int lt2 = lim2? getbit(bit[wei],B):1;
    int lt3 = lim3? getbit(bit[wei],W):1;
    int t = getbit(K,bit[wei]);
    ll res = 0;
    for(int i=0;i<=lt1;i++) {
        for(int j=0;j<=lt2;j++) {
            int x = i,y = j;
            int nc1 = c1*2 + (x-y) + t, nc2 = c2*2 + (y-x) + t;
            if(nc1 < -1 || nc2 < -1 || (x^y) > lt3) continue;
            res += dfs(wei-1,min(nc1,1),min(1,nc2),(lim1 && x == lt1),(lim2 && y == lt2),(lim3 && (x^y) == lt3));
        }
    }
    vis[wei][c1+1][c2+1][getbool(lim1)][getbool(lim2)][getbool(lim3)]= 1;
    dp[wei][c1+1][c2+1][getbool(lim1)][getbool(lim2)][getbool(lim3)] = res;
    return res;
}

int main() {
    bit[0] = 1;
    for(int i=1;i<=35;i++) bit[i] = (bit[i-1]<<1);
    int tes;
    scanf("%d",&tes);
    while(tes--) {
        scanf("%d%d%d%d",&A,&B,&K,&W);
        memset(dp,0,sizeof(dp));
        memset(vis,0,sizeof(vis));
        printf("%lld\n",dfs(35,0,0,true,true,true));
    }

    return 0;
}