【代码源每日一题div2 】简单的异或问题

小咪咪 2024-03-23 18:43 65阅读 0赞

[简单的异或问题 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![ecd03201c04540aa84dab5708d768f34.png][]

思路：

首先这有一个结论：0~2^m-1的所有数进行XOR运算后，得到的结果是0。我们来证明一下这个结论：

比如m=3时，一共是0 1 2 3 4 5 6 7，八个数，我们把他们首位组成一对，一共是4对：\{0，7\}\{1，6\}\{2，5\}\{3，4\}。

它们每一对内部进行XOR运算后的结果都是7，转化成二进制就是111，此时4个111进行XOR运算，得到的自然是0。

那么这个结论有什么用呢，我们知道111和111经过xor运算后会变成0，因为他们每一位上都是相等的，如果我们想通过111获得一个数，在这里假设我们想要的是3（二进制是011），那么就需要111和100进行XOR运算，发现了吗，100正好就是和3配对的另一个数：4.

所以，想在0~2^m-1里通过xor运算获得一个数a，就只用（2^m-1）和（2^m-1-a）进行xor运算即可，但这里要求的是最多能选多少数，我们可以把所有的数（除了目标a）都选上，真正有用的只有（2^m-1）和（2^m-1-a），至于其他的数经过运算后都会变成0.所以k能取到的最大值就是2^m-1。但有两个特殊情况，一个是a=0时，我们可以把所有的数都选上，即k=2^m,还有一个是m=1时，想获得0只能选0，想获得1可以两个都选。

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    using namespace std;
    
    const int N = 2e5 + 10;
    const int M = 3e6 + 10;
    const int P = 131;
    const int Inf = 0x3f3f3f3f;
    
    void solve() {
        int n, m;
        cin >> n >> m;
        if (n == 0 && m == 1) {
            cout << 1 << "\n";
        }else if (n == 1 && m == 1) {
            cout << 2 << "\n";
        }else {
            if (n == 0) {
                cout << (1ll << m);
            }else {
                cout << (1ll << m) - 1ll << "\n";
            }
        }
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(nullptr);
    
    	int t = 1;
    	while(t --) {
    		solve();
    	}
    	return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/11/problem/732
[ecd03201c04540aa84dab5708d768f34.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/65a062dbe4b542f79ec922d739d384ac.png