STAOI G Round 4 T1题解

特解

先来考虑方程 \(\begin{cases}x+y=A\\x \operatorname{AND} y =B\end{cases}\) 的一组特解。 由于按位与不进位，并且 \(a \operatorname{AND} b=1\) 当且仅当 \(a=b=1\) ,这意味这 \(B\) 的二进制中有一位为 \(1\)，\(x,y\) 相应的位上必定也为 \(1\)，如果这位是 \(0\)，那么只要保证 \(x,y\) 中相应的位上不同时为 \(1\) 就行。因此，我们可以先构造出一个满足 \(a \operatorname{AND} b =B\)的最小解，方法是：

• 将 \(B\) 进行二进制分解，枚举其中的每一位。

• 如果这一位为 \(1\)，则把 \(a,b\) 相应的位上变为 \(1\)。

• 如果这一位是 \(0\)，就把 \(a,b\) 中相应的位保持 \(0\)。 最后得到的 \(x,y\) 就是满足 \(a \operatorname{AND} b =B\) 并且最小的 \(a,b\)。此时，我们改变 \(a\) 中任意一位为 \(0\) 的位并不会改变 \(a \operatorname{AND} b\) 的值，而改变第 \(i\) 位相当于给这个数加上 \(2^{i-1}\)，我们可以通过改变这些 \(0\) 位来补齐 \(a+b\) 和 \(A\) 之间的差值。 设 \(a\) 的二进制分解为 \(\overline{a_1a_2\cdots a_n}\)，差值 \(c\) 的二进制分解为 \(\overline{b_1b_2\cdots c_m}\)。显然，差值可以被补齐当且仅当 \(\forall i,b_i=1\) 都有 \(a_i=0\)，否则这一位无法被补齐。因此，我们只要检验 \((a+c) \operatorname{AND} b\) 是否仍等于 \(B\) 就行了，如果可以，那么 \(x=a+c,y=b\) 就是一组特解，否则无解。

  齐次解

  假设已经求出一组解 \(x,y\)，设 \(x=(\overline{x_1x_2\cdots x_n})_2,y=(\overline{y_1y_2\cdots y_n})_2\)（不足的位向高位填 \(0\) 补齐）。我们通过观察样例可以发现，如果 \(x_i,y_i\) 一个为 \(1\)，另一个为 \(0\)，此时交换这两个数既不会改变 \(x \operatorname{AND} y\)，也不会改变 \(x+y\)，也就是说，交换这两位后的 \(x,y\) 是一组不同的解。为了满足 \(x\le y\)，我们只要保持最高的满足上面条件的两位保持不变，只交换后面不同的两位。

求和

接下来不妨设共有 \(n\) 个不同位，\(x_i,y_i\) 是其中一组不同位（不是最高的一位 ）。由加乘原理可以得知，一共由 \(2^n\) 组解。其中，\(x_i=1,y_i=0\) 的解有 \(2^{n-1}\) 种，反过来也有 \(2^{n-1}\) 种。在计算 \(y-x\) 时，第一种情况会计算为 \[\displaylines{(\overline{x_1x_2\cdots 1 \cdots x_n})_2-(\overline{y_1y_2\cdots 0 \cdots y_n})_2\\=(\overline{x_1x_2\cdots 0 \cdots x_n})_2-(\overline{y_1y_2\cdots 0 \cdots y_n})+(1-0)*2^{n-i}\\=(\overline{x_1x_2\cdots 0 \cdots x_n})_2-(\overline{y_1y_2\cdots 0 \cdots y_n})+2^{n-i}}\]后一种情况会计算为 \[\displaylines{(\overline{x_1x_2\cdots 0 \cdots x_n})_2-(\overline{y_1y_2\cdots 1 \cdots y_n})_2\\=(\overline{x_1x_2\cdots 0 \cdots x_n})_2-(\overline{y_1y_2\cdots 0 \cdots y_n})+(0-1)*2^{n-i}\\=(\overline{x_1x_2\cdots 0 \cdots x_n})_2-(\overline{y_1y_2\cdots 0 \cdots y_n})-2^{n-i}}\]两者在相加时抵消。其它不同位也一样。因此，最后不同位并不会对最终答案有影响，最终答案是将 \(x,y\) 除去不同位后相减，在乘上 \(2^n\)，最后对 \(m\) 取模后的结果。

AC Code

#include <iostream>

#include <vector>

#include <bitset>
#include <utility>
#include <cmath>

using namespace std;

const int N=65;
unsigned long long a,m,t;
typedef unsigned long long ull;
typedef long long ll;

bitset<N> binary_fact(ull a){ //二进制分解
    bitset<65> ret;
    for(ull i=0;a;a>>=1,i++){
        ret[i]=a&1;
    }
    return ret;
}

ull lpow(ull a,ull b,ull p){ //快速幂
    ull ans=1;
    for(ull i=1;b;b>>=1,i*=2){
        ans*=pow(a,(b&1)*i);
        ans=ans%m;
    }
    return ans;
}

vector<int> alyze(const bitset<N>& a,const bitset<N>& b){ //求出所有不同位的下标
    vector<int> x;
    for(int i=0;i<N;i++){
        if(a[i]^b[i])x.push_back(i);
    }
    if(!x.empty())x.pop_back();
    return x;
}

ull cau(bitset<N> a,bitset<N> b,vector<int> al){ //求结果
    for(auto x:al){
        a[x]=b[x]=0;
    }
    ull x=a.to_ullong(),y=b.to_ullong();
    ull ans=((max(x,y)-min(x,y))%m)*(lpow(2,al.size(),m));
    return ans%m;
}

pair<ull,ull> spe_sol(bitset<N> a,bitset<N> b){ //特解
    ull x=0,y=0;
    for(int i=0;i<N;i++){
        if(b[i]==1)x+=(1ull<<i),y+=(1ull<<i);
    }
    if(x+y>a.to_ullong())return make_pair(0,0);
    auto t=a.to_ullong()-x-y;
    if(((x+t)&y)!=b.to_ullong())return make_pair(0,0);
    return make_pair(x+t,y);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>t>>m;
    for(ull i=0;i<t;i++){
        ull a,b;
        cin>>a>>b;
        auto z=spe_sol(binary_fact(a),binary_fact(b));
        bitset<N> p=z.first,q=z.second;
        vector<int> k=alyze(p,q);
        cout<<cau(p,q,k)<<endl;
    }
    return 0;

}