算法竞赛进阶指南0x01 位运算

a^b

题目链接http://oj.daimayuan.top/course/13/problem/565
边界问题：b=0并且p=1的时候，快速幂板子返回的是1，实际是0，在qmi()后面%p就可以了，或者在qmi()板子里面初始化成LL res = 1 % p;

#include

using namespace std;
typedef long long LL;

LL qmi(LL a, LL b, LL mod){
	LL res = 1;
	while(b){
		if(b&1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

int main(){
	int a, b, p;
	scanf("%d %d %d", &a, &b, &p);
	printf("%d\n", qmi(a, b, p) % p);
	return 0;
}

起床困难综合症

参考：https://www.acwing.com/solution/content/15383/
1. 常见的一种二进制贪心(和&,|,^搭配)，二进制越靠前的位权重越大，能使得前面的位为1，就使得前面的位为1，否则后面就算全是1也弥补不回来
2. 按位考虑，&,|,^这些运算只和当前位相关，和其他位无关，所以可以按位考虑，而且这样枚举的情况可以从n->logn
3. 如何确定当前枚举到的位能不能选1，如果在枚举前面的时候，n中可以是1，但是最终选择了0，后面就可以随便选了，使用last标记下即可

#include

using namespace std;
typedef long long LL;
const int N = 1e5+10;
int op[N], x[N];
int n, m;

int cal(int t, int i){
	int res = t << i;
	for(int j = 1; j <= n; j ++){
		if(op[j] == 1){
			res = res & (x[j] & (1 << i));
		}
		else if(op[j] == 2){
			res = res | (x[j] & (1 << i));
		}
		else{
			res = res ^ (x[j] & (1 << i));
		}
	}	
	return res;
}
int main(){
	
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++){
		char s[4];
		scanf("%s %d", s, &x[i]);
		if(s[0] == 'A') op[i] = 1;
		else if(s[0] == 'O') op[i] = 2;
		else op[i] = 3;
	}

	int res = 0;
	int last = 0;
	for(int i = 31; i >= 0; i --){
		if(last || (m >> i & 1)){
			int A = cal(1, i), B = cal(0, i);	
			if(A > B) res += A;
			else res += B, last = 1;		
		}
		else res += cal(0, i); 
	}

	printf("%d\n", res);


	return 0;
}