快速幂问题

求\(a\)的\(b\)次方对\(p\)取模的值，\(1<=a,b,p<=10^9\)

• 典型快速幂解法， b&1为真，表示为奇数，b>>=1右移1位，表示除2

long long solve(long long a, long long b, long long p){
    long long ans = 1;
    while(b){
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

• 从二进制的角度看，实际是将b表示为二进制的按权展示式

  \(b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+...+c_02^0\) ，\(a^b=a^{c_{k-1}2^{k-1}}*a^{c_{k-2}2^{k-2}}*...*a^{c_02^0}\)

• 同时注意到！！b&1可以取出b的二进制表示的最低位，b>>=1可以去除最低位，于是可以从0号位遍历每个数位进行累积运算！！

long long solve(long long a, long long b, long long p){
    long long ans = 1;
    for(;b;b>>=1){
        if(b & 1) ans = ans * a % p; //为1时才累计进ans
        a = a * a % p; //更新次幂
    }
    return ans;
}

求a乘b对p取模的值，其中1<=a,b,p<=10^18

• 由于可能超过long long当然不能直接乘，可以利用位运算的思想，将b表示为二进制的按权展开式

  \(b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+...+c_02^0\) ，\(a*b=c_{k-1}*a*2^{k-1}+...+c_0*a*2^0\)

• 递推\(k\)次可以求出答案，同时，每一项都不会超过long long的范围！！

• 注意到！！b&1可以取出b的二进制下最低位，b>>=1可以

• 只有取出的位为1才将结果累加到ans上，每次都要更新次幂，这里更新方式是a = a*2

long long solve(long long a, long long b, long long p){
    long long ans = 0;
    for(;b;b>=1){
        if(b&1) ans  = (ans + a) % p;
        a = a * 2 % p;
    }
}

状态压缩

• 将长度为m的bool数组用m位二进制整数存储

• 使用bitset实现！！！

  #include<bitset>
  bitset<1000> s; //1000位的bitset
  ~s; //按位取反
  &|^; //对两个位数相同的bitset执行按位与，按位或，按位异或
  >>,<<;//右移，左移
  ==,!=;//大小比较
  s[k]; //支持下标访问
  s[k]^=1; //第k位取反
  s.count(); //多少位为1
  s.any(); //任意一位为1都返回true
  s.none();//所有位为0才返回true
  s.set(); //所有位置1