算法竞赛进阶指南0x01位运算题解

a^b

背景知识：

1.快速幂

已知任意数字均可由二进制表示，即为，给定一个十进制整数b，若其在二进制表示下有k位，则其可以被表示为 $b=\sum_{i=0}^{k-1}c_i2^{i}$ 其中 $c_i$ 为b在二进制表示下的第i位

根据幂次运算的运算律，同底数幂相乘，底数不变，指数相加，即 $base^{a+b}=base^a*base^b$ 可得公式

$a^b=\prod_{i=0}^{k-1}a^{c_i2^i}$
2.取模运算的分配律

即为

(a+b) % p = ( a % p + b % p ) % p

((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p

结合一下，很简单得到了快速求幂次的快速幂方法

时间复杂度为 $O(log_2b)$

即为b的二进制表示位数

#include<cstdio>
long long mod;
long long pow(long long a, long long b) {
    long long ans = 1;
    long long base = a%mod;
    while (b > 0) {
        if (b & 1) {
            ans *= base;
            ans%=mod;
        }
        base *= base;
        base %=mod;
        b>>=1;
    }
    return ans%mod;
}
int main(void){
    long long a,b;
    scanf("%lld%lld%lld",&a,&b,&mod);
    printf("%lld\n",pow(a,b));
    return 0;
}

Raising Modulo Numbers

和上题同理，求了一下和

#include<cstdio>
using namespace std;
long long pow(long long a,long long b,long long mod){
    long long ans=1;
    long long base=a;
    while(b){
        if(b&1){
            ans*=base;
            ans%=mod;
        }
        base=base*base;
        base%=mod;
        b>>=1;
    }
    return ans%mod;
}
int main(void){
    long long t;
    scanf("%lld",&t);
    while(t--){
        long long mod,ans=0,a,b;
        scanf("%lld",&mod);
        long long n;
        scanf("%lld",&n);
        for(long long i=0;i<n;i++){
            scanf("%lld%lld",&a,&b);
            ans+=pow(a,b,mod);
            ans%=mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

64位整数乘法

类似于快速幂的思想

$b=\sum_{i=0}^{k-1}c_i2^{i}$ 其中 $c_i$ 为b在二进制表示下的第i位

相似的，根据乘法的运算律 $(a+b)*c=a*c+b*c$

所以 $a*b=a*(\sum_{i=0}^{k-1}c_i2^{i})=\sum_{i=0}^{k-1} a*c_i*2^{i}$

时间复杂度为b的二进制长度 $O(log_2b)$

#include<cstdio>
long long mul(long long a, long long b, long long m) {
    a%=m;
    b%=m;
    long long ans = 0;
    while (a > 0) {
        if (a & 1) {
            ans += b;
            ans %= m;
        }
        b*= 2;
        b%= m;
        a >>= 1;
    }
    return ans % m;
}
int main(void) {
    long long a, b, p;
    scanf("%lld%lld%lld", &a, &b, &p);
    long long ans = mul(a, b, p);
    printf("%lld", ans);
    return 0;
}

最短Hamilton路径

Hamilton路径就是从0到n-1不重复的经过每个点一次

我们可以引入一个叫做状态压缩的概念

因为在计算机中，数字以二进制存储，所以位运算往往速度很快

对于n个城市，我们可以用一个n位的二进制数来表示这n个点的状态

举个例子

对于五个城市，二进制数 10010，表示第二个和第五个城市的状态为1，即为已经走过这两个城市，第1，3，4城市为0，表示没有走过这三个城市

所以我们可以利用一个二维数组F[i,j]其中i的二进制数表示了当前走过哪些城市，j表示当前在哪座城市，即为上一步走的城市

在起点时，有f[1,0]=0，因为还没出发，只经过了点0，并且距离为0

然后我们一直对i进行枚举即可

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long dp[1 << 20][20];
long long dis[21][21];
int main(void) {
    int n;
    scanf("%d", &n);
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%lld", &dis[i][j]);
        }
    }
    dp[1][0] = 0;
    for (int i = 0; i < 1 << n; i++) {//状态的枚举
        for (int j = 0; j < n; j++) {//当前在j城市
            if ((i >> j) & 1) {//走过当前城市
                for (int k = 0; k < n; k++) {//枚举下一步要去的城市
                    if (~(i >> k) & 1) {//下一个没走
                        dp[i + (1 << k)][k] = min(dp[i + (1 << k)][k], dp[i][j] + dis[j][k]);
//i+(1<<k)为当前走过的城市状态+第k个城市左移，即为当前走过的城市+要去的城市，他的距离就是走过i个城市，上一步在j城市，加上从j城市到k城市的最小值，即为状态转移方程
                    }
                }
            }
        }
    }
    printf("%lld", dp[(1 << n)-1][n - 1]);
    return 0;
}