位运算的简单应用

位运算的简单应用

基本概念

  • int a = 1; 变量a实际的表示为0000…0001,共32位
  • 右移>>n位:去掉二进制后的n位
  • 左移<<n位:在二进制数后面填上n个0,$(1 << n = 2^n)$
  • 按位与或非

    应用1——快速幂

例如:计算$7^{10}$

先算$7\times7$得$49$,则$7^5$为$49\times49\times7$,再算它的平方,共进行了4次乘法。

模仿这样的过程,我们得到一个在$O(\log n)$时间内计算出幂的算法,也就是快速幂。

对于实现,我们可以使用二进制来达到非递归的快速幂。

$7^{10}=7^{(1010)_2}=7^{(1000)_2}\times7^{(10)_2}$

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef long long ll;
const ll MOD = 998244353;
ll powmod(ll a,ll b){
ll ans = 1;
a = a % MOD;
assert(b >= 0);
while (b){
if (b & 1) ans = ans * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return ans;
}

应用2——快速乘

和快速幂的思想相同,只是原来的乘“换成了“加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ull a,b,p;cin >> a >> b >> p;
ull ans = 0;
while (b){
if (b&1) ans = (ans + a) % p;
a = a * 2 % p;
b >>= 1;
}
cout << ans << endl;
return 0;
}

应用3——状态压缩DP

题目描述

给定一张 $n$ 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数$n$。

接下来$n$行每行$n$个整数,其中第i行第j个整数表示点i到j的距离(记为$a[i,j]$)。

对于任意的$x,y,z$数据保证 $a[x,x]=0, a[x,y]=a[y,x] $并且 $a[x,y]+a[y,z]≥a[x,z]$。

输出格式

输出一个整数,表示最短Hamilton路径的长度。

数据范围

$1≤n≤20$
$0≤a[i,j]≤107$

AC代码

时间复杂度$O(2^n\cdot n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

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

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0;i < n;++i){
for (int j = 0;j < n;++j){
cin >> mp[i][j];
}
}
// 在第一个点,只有第一个点被选了
//000...001 0
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){
for (int k = 0;k < n;++k){
if (i - (1 << j) >> k & 1){
dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + mp[k][j]);
}
}
}
}
}
cout << dp[(1 << n) - 1][n-1] << endl;
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×