开坑。
1-位运算
我们知道，C++中的位运算有：&、|、^、~、>>、<<。
应用:
1-1快速幂：
int qpow(int a,int b,int p)
{
int vis=a;
int sum=1;
while(b)
{
if(b&1)
{
sum*=vis;
sum%=p;
}
vis*=vis;
vis%=p;
b>>=1;
}
return sum;
}
不妨模拟一下上述过程。
假设开始，我们 \(a=5\)，\(b=10\)，\(p=998244353\)，即求 \(5^{10}\mod 998244353\) 的值。
最初，我们的 \(vis=5\),\(sum=1\)。
第一次循环：
可以发现，\(b\) 作为一个二进制数时，它的表示是 \((1010)_{2}\)。
而 \(1\)，显然为 \((0001)_{2}\)。
因此这里 b&1 的结果为 0000，即 \(0\)。
所以这里跳过乘的过程。
这时候 \(vis\)变成 \(vis^2\),即 \(10\)，然后 \(b\) 右移。
第二次循环：
可以发现，\(b\) 作为右移后时，它的表示是 \((101)_{2}\),因此这里 b&1 的结果为 001，即 \(1\)。
进入乘的过程，让 \(sum*vis\)，此时\(sum=10\)，然后重复 \(vis\) 变成 \(vis^2\),然后 \(b\) 右移。
重复之后发现，显然结果正确。
时间复杂度 \(\log n\)。
1-2 状态压缩
不会状态压缩动态规划，我还不会状态压缩吗？
不会。