位运算

补码： x + y = 00000000...00

x的补码： ~x + 1

对 f 数组赋值成无穷： memset(f, 0x3f, sizeof f);足够大且不会溢出整数

移位：1 << n = 2 ^ n,n >> x = n / 2 ^ x

1.快速幂求a^b%p

O(logn)

int qmi(int a, int b, int p) {
	int res = 1 % p;
    while (b) {
        //从b的个位开始考虑
    	if (b & 1) res = res * 1ll * a % p;
    	//每次以a平方递增
    	a = a * 1ll * a % p;
    	//去掉个位
        b >>= 1;
    }
    return res;
}

2.求a*b%p

ULL mul(ULL a, ULL b, ULL p) {
    ULL res = 0;
    while (b) {
        //个位数
        if (b & 1) res = (res + a) % p;
        //a倍增
        a = a * 2 % p;
        //去掉个位数
        b >>= 1;
    }
    return res;
}