11.5 cometoj #12 -- D XOR Pair （数位dp）

题目：XOR Pair

分析： 官方题解看不太懂 ，还是套平常的板子做；

分析 |x-y| 的数位，用dp[pos][v1][v2]存满足条件的pair(x,y)的个数

按二进制位分析，最多有64位,所以pos==64

条件限制 ：

1. x^y == n ，对数位来说即每一位都有 [x]^[y] == [n] ，很常见的限制了，在循环里处理即可（但题解说这道题换成x&y==n 或 x|y == n 就会很麻烦？）

 2.| x - y | <= m;

即 x-y <= m && x-y >= -m ，

即 m-x+y >= 0 && m+x-y >= 0

其中 x 可取 0 ， 1 ，y可取 0 ， 1

对于这两个式子数为分析 ，每一位可能是0 ，-1 ，1 ，2 四种情况 ，若不考虑进位（二进制dp常用处理 ）：

若 [高位] >= 1 , 后面数位就算全取-1最后结果还满足条件 ，x，y取值不受限制，此位就算大于1也可以按1考虑

若 [高位] < -1 ,后面就算全取2也一定不行 ，所以直接返回0就行；

综上 ，这两个式子的数位上的取值 有 -1 ， 0 ，1 三种取值 ，记为 状态[v1][v2] ,v1==3 ,v2==3;

3. 0 <= x <= a ,0<=y <=b ，直接用两个边界标记limx ，limy 进行特判即可

分析完条件限制就能进行数位dp了：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <unordered_map>
#define mem( a ,x ) memset( a , x ,sizeof(a) )
#define rep( i ,x ,y ) for( int i = x ; i<=y ;i++ )
#define lson l ,mid ,pos<<1
#define rson mid+1 ,r ,pos<<1|1
#define Fi first
#define Se second

using namespace std;
typedef long long ll ;
typedef pair<int ,int> pii;
typedef pair<ll ,int> pli;
const ll inf = 0x3f3f3f3f;
const int N = 1e5+5;
const ll mod = 1e9+7;

int num_n[64] ,num_a[64] ,num_b[64] ,num_m[64];
ll dp[64][3][3];
ll a ,b ,n ,m;

void div( int * num ,ll x ){

    rep( i ,0 ,63 ){
        num[i] = x&1;
        x >>= 1;
    }
    //for( int i = 63 ; i>=0 ;i-- )printf("%d" ,num[i] );
    //cout<<endl;
    return;
}

ll dfs( int pos ,ll v1 ,ll v2 ,bool limx ,bool limy ){
    // v1 --- m-x+y ; v2 --- m+x-y ;
    v1 = min( v1 ,1ll );v2 = min( v2 ,1ll );
    
    //cout<<pos<<" "<<v1<<" "<<v2<<" "<<limx<<" "<<limy<<endl;
    // 最高位只要为1后面就为所欲为了
    // 即 二进制 ： 1 -1 -1 -1 -1 -1 -1 一定 >= 0;
    if( v1 < -1 || v2 < -1 )return 0;
    //道理同上 ，最高位只要为-2后面怎么搞都不行
    
    if( pos < 0 ){
        return v1 >= 0 && v2 >= 0;
    }
    if( !(limx || limy) && dp[pos][v1+1][v2+1] != -1 )
        return dp[pos][v1+1][v2+1];

    int upx = limx ? num_a[pos] : 1;
    int upy = limy ? num_b[pos] : 1;
    ll ret = 0;

    rep( i ,0 ,upx )
    rep( j ,0 ,upy ){
       if( (i^j) != num_n[pos] )continue;
       // 逐位运算分析 ，进制 数位 与 权重 ，感受一下
       ll vv1 = v1*2 + num_m[pos] - i + j;
       ll vv2 = v2*2 + num_m[pos] + i - j;
       // 想一想：这里状态转移与 十进制 和 取模 的时候的状态转移有什么相同和不同？
       ret += dfs( pos-1 , vv1 ,vv2 , limx & (i==upx) , limy & (j==upy) );
    }

    if( !(limx || limy) )dp[pos][v1+1][v2+1] = ret;
    return ret;

}

int main( ){
    int t;
     scanf("%d" ,&t);
     while( t-- ){
         mem( dp ,-1 );
         // dp[pos][v1][v2]
         // 状态 v1 -- pos位的 m-x+y
         // 状态 v2 -- pos位的 m+x-y
         // m影响 v1 ,v2 所以不能复用
         scanf("%lld%lld%lld%lld" ,&a ,&b ,&n ,&m );
         div( num_n ,n );
         div( num_a ,a );
         div( num_b ,b );
         div( num_m ,m );
         printf("%lld
" ,dfs(63 ,0 ,0 ,1 ,1) );
     }
     return 0;
}

 

// 想一想：这里状态转移与 十进制 和 取模 的时候的状态转移有什么相同和不同？

//想一想：这里状态转移与十进制和取模的时候的状态转移有什么相同和不同？

轻灵划译

数据来源: