开坑。
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 状态压缩
不会状态压缩动态规划,我还不会状态压缩吗?
不会。