# 算法竞赛进阶指南-0x01基本算法-位运算

a^b 快速幂

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

ll a, b, p;

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

int main(){
__;
cin >> a >> b >> p;
ll ans = qpow(a, b, p);
cout << ans << endl;
return 0;
}



64位整数乘法

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

ll a, b, p;

ll qmul(ll a, ll b, ll p){
ll ans = 0ll;
while(b){
if(b & 1)   ans = (ans + a) % p;
a = (a + a) % p;
b >>= 1;
}
return ans;
}

int main(){
__;
cin >> a >> b >> p;
ll ans = qmul(a, b, p);
cout << ans << endl;
return 0;
}



Solution: 状压DP
F[i][j] 表示：所有从 0 走到 j ,走过的所有点的情况是 i 的所有路径。
F[i][j] = min(F[i][j], F[i - (1 << j)][k] + w[k][j])

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int n;
int w[21][21];
int f[1 << 21][21];

int main(){
__;
cin >> n;
for(int i = 0; i < n; i ++){
for(int j = 0; j < n; j ++){
cin >> w[i][j];
}
}
memset(f, 0x3f, sizeof(f));
f[1][0] = 0;
for(int i = 0; i < 1 << n; i ++){//i表示所有的情况
for(int j = 0; j < n; j ++){//j表示走到哪一个点
if(i >> j & 1){
for(int k = 0; k < n; k ++){//k表示走到j这个点之前,以k为终点的最短距离
if(i >> k & 1) {
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
}
}
}
}
}
printf("%d\n", f[(1 << n) - 1][n - 1]);
return 0;
}



Solution: 由于题目中只有与、或、异或三种不进位的位运算，所以直接枚举每一位填0还是1。

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

bitset<31> one, zero;
int n, m, x;
string s;

int main(){
__;
cin >> n >> m;
one.set();
zero.reset();
while(n --){
cin >> s >> x;
if(s == "AND"){
one &= x;
zero &= x;
}
else if(s == "OR"){
one |= x;
zero |= x;
}
else{
one ^= x;
zero ^= x;
}
}
int ans = 0;
for(int i = 0; i < 31; i ++){
if(zero[i] == 1){
ans += (1 << i);
}
else if(one[i] == 1 && (1 << i) + ans <= m){
ans += (1 << i);
}
}
printf("%d\n", ans);
return 0;
}