一两句话小技巧

二进制枚举子集

int S = 11; // 1011b
for(int x=S; x>0; x=(x-1) & S) // do something
// 1. x = 1011 2. x = 1010 3. x = 1001
// 4. x = 1000 5. x = 0011 6. x = 0010
// 7. x = 0001 8. x = 0000

求余$O(1)$快速乘

当两个long long相乘会溢出，又不能用__int128_t时使用。

当mod过大时可能出现精度问题。

不使用四舍五入

ll mul_mod(ll a, ll b, ll mod){
    return (a*b-(ll)((long double)a/mod*b)*mod+mod)%mod;
}

使用四舍五入

ll mul_mod(ll a, ll b, ll mod){
    ll c = a*b-(ll)((long double)a/mod*b + 0.5)*mod;
    return c<0?c+mod:c;
}

原理：

$a*b\mod p = a * b - \lfloor\frac{a*b}{p}\rfloor *p$

令$d = \lfloor\frac{a*b}{p}\rfloor$，最终结果为$c=a*b-d*p$，明显a*b与d*p都可能会溢出（即对$2^{63}$取模），但他们的差值一定在long long的范围内（差值的绝对值小于$p$）。