算法竞赛进阶指南-位运算

很久没更新简书了，今日回归，要是还有小伙伴能看见，请监督我，我越来越菜了QAQ！

1. a^b
   题目链接https://ac.nowcoder.com/acm/contest/996/A
   快速幂裸题。

#include<iostream>
using namespace std;

int main() {
    long long a, b, p;
    cin>>a>>b>>p;
    long long res = 1 % p;
    a %= p;
    while(b) {
        if(b & 1) res = (res * a) % p;
        a = (a * a)%p;
        b >>= 1;
    }
    cout<< res<<endl;
    return 0;
}

2. 64位整数乘法
   题目链接https://ac.nowcoder.com/acm/contest/996/C
   快速幂变形。

#include<iostream>
using namespace std;

int main() {
    long long a,b,p;
    cin>>a>>b>>p;
    long long res = 0 % p;
    while(b) {
        if(b & 1) res = (res + a) % p;
        a = (a%p + a%p) % p;
        b >>= 1;
    }
    cout<<res<<endl;
    return 0;
}

3. 最短Hamilton距离
   题目链接https://ac.nowcoder.com/acm/contest/996/D
   状压dp
   dp[1<<20][N]
   其中第一维代表的是状态，哪些点已经遍历过，每一位的0或者1代表当前点是否被遍历。
   第二维代表当前遍历过程中，走到了哪个点。
   dp状态转移公式：
   dp[state][j] = dp[state_k][k] + weight[k][j] , state_k = state 除掉j之后的集合，其中 state_k要包含k。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 20,M = 1 <<20;
int n;
int dp[M][N],weight[N][N];

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0;j < n;j++) {
            cin>>weight[i][j];
        }
    }
    memset(dp,0x3f,sizeof dp);
    dp[1][0] = 0;
    for(int i = 0;i < 1<<n;i++) {
        for(int j = 0; j < n; j++) {
            if(i >> j & 1) { // 判断当前状态是否可以停在j点
                for(int k = 0; k < n;k++) {
                    if((i - (1<<j)) >> k & 1) { // 判断当前状态去除j之后，是否包含k
                        dp[i][j] = min(dp[i][j], dp[i-(1<<j)][k] + weight[k][j]);
                    }
                }
            }
        }
    }
    cout<<dp[(1<<n) - 1][n-1]<<endl;
    return 0;
}

4. lowbit实现

int lowbit1(int n) {
     return (~n + 1) & n;
}

int lowbit2(int n) {
     return (-n) & n;
}