简单的异或问题 - 题目 - Daimayuan Online Judge
题意:
思路:
首先这有一个结论: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 longusing 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;
}