位运算的应用

快速幂

题目：

a^b

快速幂讲解

假设我们要计算 $3^{11}$

这个当然可以用暴力的方式去算，没啥问题，那这样就要算11次，即n次

可以看一下11的二进制为1011

$3^{11} = 3^8*3^2*3^1$

这个结果很显然，可以得出11的二进制中对应1的位置，恰好为 $3^{11}$ 的一个因素，这是不是巧合呢？我们不妨再尝试一个

30的二进制为11110

$10^{30} = 10^{16}*10^{8}*10^4*10^2$

显然这不是一个巧合。

而我们可以看出，二进制指数的计算过层是可以被简化的

比如 $10^{16} = 2^{8}*2^{8}$ ，在前面的计算过程中，我们又可以通过 $2^4$ 计算出 $2^8$ 。

这就是快速幂的思想了

AC代码：

#include <iostream>
using namespace std;
// 为了以后方便使用就做成模板的形式了
// 计算a^b，为什么要有个c呢，因为次方计算通常很大，需要取膜避免溢出
int quick_mi(int a,int b,int c){
    // 避免指数为0的情况
    int res = 1%c;
    // 用为运算的方式遍历b的每一位，直至遍历完所有为1的位置，即原来的数字变为0
    while(b){
        // 如果当前位为1
        if(b&1){
            // 这里1ll是表示longlong型的1，避免溢出
            res = res*1ll*a%c;
        }
        // 计算下一个幂
        a = a*1ll*a%c;
        // 获取b的下一位
        b >>= 1;
    }
    return res;
}
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    cout<<quick_mi(a,b,c)<<endl;
    return 0;
}

快速乘

64位整数乘法

解题思路：

这题呢，他的数据真的很大，光是接收输入都需要unsigned long long来读取了何况乘法，你就别想着把它计算出来再取膜了。

这题跟快速幂类似

幂可以用乘法表示，那乘法不就可以用加法表示嘛，举个例子:计算 $3 \times 11$

可以看一下11的二进制为1011

$33=3 * 11 = 3*1 + 3*2+3*8 = 3+6+24=33$

真巧呢

AC代码

#include <iostream>
using namespace std;
typedef unsigned long long ULL;
int main(){
    ULL a,b,p,res=0;
    cin>>a>>b>>p;
    while(b){
        if(b&1) res = (res+a)%p;
        b>>=1;
        a = a*2%p;
    }
    cout<<res<<endl;
    return 0;
}

最短hamilton路径

解题思路

hamilton路径，就是走完所有的点一次，题目就是要求最短的

所以我们其实是可以发现，这n个点里，无论怎么走只要，走完所有的点就可以了

抓住两个要点：

当前状态数（最多有20个节点）对应20位，每一位有0或1两种可能，所以需要 $2^{20}$
当前终点的可能有20种选择

最大计算应该位 $2^{20}*20$ 约为 $2*10^8$ 在可接受范围内

令f[status][j]表示选中了status二进制对应位上的点，并且终点位j的最短距离

寻找是否存在k，使得从status-k的状态先到k，再到j的情况j的情况最小

我们可以得到递推方程：

1	f[status][j] = min(f[i][j],f[status-k][k]+weight[k][j])

最后的结果为，status每一位都选中，到第n-1个点的距离最短，即f[status][n-1]

ac代码

#include <bits/stdc++.h>
using namespace std;
const int N = 20,M = 1<<20;
int n;
// 图的权重和结果存储
int weight[N][N],f[M][N];
int main(){
    cin>>n;
    for(int i = 0;i<n;i++)
        for(int j = 0;j<n;j++)
            cin>>weight[i][j];
    memset(f,0x3f,sizeof f);
    // 在0号点到0号点的距离为0
    f[1][0] = 0;
    // 遍历点集的各种组合方式
    for(int i = 1;i<(1<<n);i++){
        // 遍历当前组合下的每一位
        for(int j = 0;j<n;j++){
            // 如果当前组合方式的第j位被选中了
            if((i>>j)&1)
                // 再去第j位之前，先去第k位，看看直接去i第j位的代价和先去k位再去j位的代价哪一个更大
                for(int k = 0;k<n;k++){
                    // 确定第k位是否被选中
                    if(i-(1<<j)>>k &1)
                        // 确定从i去j的最佳路径
                        f[i][j] = min(f[i][j],f[i-(1<<j)][k]+weight[k][j]);
                }
        }
    }
    // 每一位都被选中了，要到第n-1个点的最优路径
    cout<<f[(1<<n)-1][n-1]<<endl;
    return 0;
}

起床困难户

解题思路

我们都知道，结果res是经过一系列的位运算得到的，并且位运算不会进位，也就是说，为运算结果的res只和当前x对应的位的数值有关

对于最优值，初始状态，无非都是每一位全为0(none)，或者每一位全为1(one)

在输入每一扇门的时候都将none,one进行对应的计算

如果第i位为1，说明在该种初值情况下，i这一位是需要的

答案中对应位的1越多越好

如何选择对应的位加入到res中呢，主要有两个原则：

如果开始是0，最后变成了1（伤害变多了），那必选啊
如果开始是1，最后还是1，如果该位表示的数，没有超过最大攻击力，可以加
如果开始是0结果还是0，开始是1结果变成0，那这一位没必要了

AC代码

#include <bits/stdc++.h>
using namespace std;
// 因为最大值是1e9,这个n刚好比2^30小，所以使用30位
const int N  =30;
int main(){
    int n,m;
    bitset<40> one,none;
    // 初始全为1和全为0
    one.set();
    none.reset();
    cin>>n>>m;
    for(int i =0 ;i<n;i++)
    {
        // 对每个数都进行对应的操作
        string a;
        int b;
        cin>>a>>b;
        if(a == "AND")one &= b,none &=b;
        else if(a == "OR") one |=b,none |=b;
        else one ^=b,none ^=b;
    }
    // 初始化结果
    int res = 0;
    for(int i =0;i<N;i++){
        // 如果开始为0最后变成了1，（伤害变多）一定要选
        if(none[i] == 1)
            res += (1<<i);
        // 如果一开始为1最后还是1，那么如果他初始攻击力比这一位对应的攻击力大，加上加上
        else if(one[i] == 1 && m >= (1<<i))
            res += (1<<i);
    }
    cout<<res<<endl;
    return 0;
}