STAOI G Round 4 T1题解

特解

先来考虑方程 的一组特解。 由于按位与不进位，并且 当且仅当 ,这意味这 的二进制中有一位为 ， 相应的位上必定也为 ，如果这位是 ，那么只要保证 中相应的位上不同时为 就行。因此，我们可以先构造出一个满足 的最小解，方法是：

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

• 如果这一位为 ，则把 相应的位上变为 。

• 如果这一位是 ，就把 中相应的位保持 。 最后得到的 就是满足 并且最小的 。此时，我们改变 中任意一位为 的位并不会改变 的值，而改变第 位相当于给这个数加上 ，我们可以通过改变这些 位来补齐 和 之间的差值。 设 的二进制分解为 ，差值 的二进制分解为 。显然，差值可以被补齐当且仅当 都有 ，否则这一位无法被补齐。因此，我们只要检验 是否仍等于 就行了，如果可以，那么 就是一组特解，否则无解。

  齐次解

  假设已经求出一组解 ，设 （不足的位向高位填 补齐）。我们通过观察样例可以发现，如果 一个为 ，另一个为 ，此时交换这两个数既不会改变 ，也不会改变 ，也就是说，交换这两位后的 是一组不同的解。为了满足 ，我们只要保持最高的满足上面条件的两位保持不变，只交换后面不同的两位。

求和

接下来不妨设共有 个不同位， 是其中一组不同位（不是最高的一位 ）。由加乘原理可以得知，一共由 组解。其中， 的解有 种，反过来也有 种。在计算 时，第一种情况会计算为 后一种情况会计算为 两者在相加时抵消。其它不同位也一样。因此，最后不同位并不会对最终答案有影响，最终答案是将 除去不同位后相减，在乘上 ，最后对 取模后的结果。

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;

}