位运算
1、a*b%p
方法一：将b用二进制表示然后递推累乘
for(; b; b >>= 1)
{
ans = (ans + (b & 1) * a % p) %p;
a = a * 2 % p;
}
方法二：将ab mod p 转换成 ab - ⌊ab/p⌋ * p 令c = ⌊ab/p⌋；
用long double存储ab/p，再转化成ull，便可做到向下取整的作用（当ab % p == 0，时c比实际小一），因此在最后需要判断ans = ab - cp的正负，若ans<0，需要再加一个p
ull c;
c = (long double) a * b / p;
ull x = a*b, y = c*p;
ans = (ll)(x%p) - (ll)(y%p);
if(ans < 0) ans += p;
2、二进制状态压缩
STL:bitset
1、取出整数n在二进制表示下的第k位:(n >> k) & 1
2、取出整数n在二进制表示下的后k位:n & ((1 << k) - 1)
3、把整数n在二进制表示下的第k位取反:n xor (1 << k) s.flip(k)
4、对整数n在二进制表示下的第k位赋值1:n | (1 << k) s.set(k, v)
5、对整数n在二进制表示下的第k位赋值0:n & (~(1 << k)) s.reset(k)
s.count( ) 返回有多少位为1
s.none() 全为0返回true
s.any() 至少一位为1返回true
s.flip 把s所有位取反
s.set() 把s所有位变为1
s.reset() 把s所有位变为0
状态压缩DP
产生原因：利用朴素算法枚举各状态会超时，因此用二进制加位运算来表示状态，并进行一系列操作
例:acwing91 最短Hamilton路径
给定一张 n 个点的带权无向图，点从 0∼n−1标号，求起点 0 到终点 n−1的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数 n。
接下来 n 行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]）。
对于任意的 x,y,z，数据保证 a[x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。
输出格式
输出一个整数，表示最短 Hamilton 路径的长度。
数据范围
1≤n≤20，0≤a[i,j]≤107
输入样例：
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例：
18
Code：
const int M = 1 << 20, N = 20;
int f[M][N];
int n;
int w[25][25];
int main ()
{
scanf("%d", &n);
For(i, 0, n-1)
For(j, 0, n-1)
scanf("%d", &w[i][j]);
memset(f, 0x3f, sizeof(f)); //因为要求最小值，所以初始化为最大值
f[1][0] = 0; //在起点0上 (初始条件)
for(int i = 0; i < (1 << n); i++) //枚举所有的路径状态
{
for(int j = 0; j < n; j++) //枚举所有为1的点j(从k转移而来)
{
if(i >> j & 1) //判断是否为1
for(int k = 0; k < n; k++) //枚举所有为1的点k(到达点j前的终点)
if(i - (1 << j) >> k & 1) //先将此时的点j变为0,再判断第k位是否为1
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]); //状态转移方程
}
}
printf("%d\n", f[(1 << n) - 1][n-1]);
return 0;
}
用二进制表示状态
例:acwing998 起床困难综合症 NOI2014
思路：
位运算的特点：运算过程中每一位独立
再将求最大值的问题分解为求每一位最大值，利用贪心思想，尽量令最终伤害的每一位都为1；
如果初始数值的某一位为0，经过运算后为1，则是一定可以加入最终伤害的；
如果初始数值的某一位为1，经过运算后为0则舍去（因为反而令数值降低了），若为仍为1，则当满足以下条件时，就加入最终伤害
1、初始数值的该位取1后，并未超过初始上限m；
根据上述运算法则，遍历好所有二进制下的数位(只需遍历0-30位，因为m上限为\(10^9\),换算为二进制最多只有[\(log_{2}{10^9}\)])后所得的最终伤害即为最大值
代码示例：
int n, m;
int main ()
{
bitset <50> none, one;
none.reset();
one.set();
cin >> n >> m;
while(n--)
{
string s;
int num;
cin >> s >> num;
if(s == "AND") none &= num, one &= num;
if(s == "OR") none |= num, one |= num;
if(s == "XOR") none ^= num, one ^= num;
}
int sum = 0;
int ans = 0;
For(i, 0, 29)
{
if(none[i] == 1)
{
ans += (1 << i);
continue;
}
if(one[i] == 1)
{
if(sum + (1 << i) > m) continue;
sum += (1 << i);
ans += (1 << i);
}
}
cout << ans;
return 0;
}
lowbit运算
lowbit(x)返回二进制下x的最低位1以及后面的所有0所组成的数值
eg：lowbit(6)返回2 (110取10)
lowbit(x) = x & (~x + 1) = x & -x ;
利用lowbit(x)求x二进制下为1的每一位位置
int x;
int h[37];
int main ()
{
//利用hash数组h预处理2的k次方1的位值
For(i, 0, 35) h[(1ll<<i) % 37] = i; //注意1后面的ll
cin >> x;
while(x != 0)
{
cout << h[x & -x] << " ";
x -= x & -x;
}
return 0;
}
tips:可以利用\(2^k\)% MOD 来减小hash数组的大小
\(\forall{k}\in\)\([0, 35]，\)\(2^k\) mod 37 互不相等，此时MOD可取37
相关内置函数（尽量不要随便使用）
int a = __lg(x) // 返回x二进制下的
unsigned int x;
cin >> x;
int a = __builtin_ctz(x); //返回x二进制下最低位1后面0的个数
unsigned ll x;
cin >> x;
int a = __builtin_ctzll(x); //返回x二进制下最低位1后面0的个数
unsigned int x;
cin >> x;
int a = __builtin_popcount(x); //返回x二进制下有多少位为1
unsigned ll x;
cin >> x;
int a = __builtin_popcountll(x); //返回x二进制下有多少位为1