焦点报道:0X01 位运算笔记

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

焦点报道:0X01 位运算笔记

2023-02-19 15:15:59 来源：博客园

位运算，经常可以用来处理一些数学或动归方面的问题，通常会在数据范围较小的情况下使用。

【资料图】

为方便起见，一个 \(\mathrm{n}\) 位二进制数从右到左分别为第 \(\mathrm{0 \sim n - 1}\) 位。

快速幂 (\(\texttt{ACW89 a^b}\))

求 \(\mathrm{a^b}\) 对 \(\mathrm{p}\) 取模的值。

\(a, b \leq 10 ^ 9, 1 \leq p \leq 10 ^ 9\)。

考虑 \(b\) 的二进制。若可以表示为 \(\sum_{i}^{} 2^i\) 的形式，那么 \(a^b\) 就可以表示成 \(a ^ {\sum_{i}^{} 2 ^ i}\)。

而 \(a ^ {2 ^ i} = (a^{2^{i - 1}}) ^ 2\)，这样可以通过递推的方式求出 \(a ^ {2 ^ i}\)。由于 \(\max\{i\}\) 是 \(\log b\) 级别的，所以总时间复杂度为 \(O(\log b)\)。

#include #include #include #include using namespace std;using LL = long long;int qpow(int a, int b, int p) {    int ans = 1 % p; // 这里是为了避免 p = 0 的情况出现    while (b) {        if (b & 1) ans = (LL)ans * a % p;        a = (LL)a * a % p;        b >>= 1;    }    return ans;}int main() {    int a, b, p;    scanf("%d%d%d", &a, &b, &p);    printf("%d\n", qpow(a, b, p));    return 0;}

六十四位整数乘法 (\(\texttt{ACW90}\))

求 \(a * b\) 对 \(p\) 取模的值。

算法一：

我们可以用类似快速幂的思想，使用二进制优化算法。将 \(b\) 拆分成二进制来看。假设 \(b\) 拆分成二进制之后是 \(\sum 2^i\)，那么答案就是 \(a ^ {\sum 2 ^ i} = \prod a ^ {2 ^ i}\)。由于 \(\max_i \leq \log_2 b\) ，因此可以保证复杂度为 \(O(\log b)\)。

#include #include #include #include using namespace std;using LL = long long;LL mul(LL a, LL b, LL p) {    LL ans = 0;    while (b) {        if (b & 1) ans = (ans + a) % p;        a = (a << 1) % p;        b >>= 1;    }    return ans;}int main() {    LL a, b, p;    scanf("%lld%lld%lld", &a, &b, &p);    printf("%lld\n", mul(a, b, p));}

算法二：

\(a \times b \pmod p = a \times b - \left \lfloor a \times b / p \right \rfloor\) 。

因此可以使用 \(\operatorname{long double}\) 存储 \(\left \lfloor a \times b / p \right \rfloor\)，\(\operatorname{long long}\) 存储 \(a \times b\)。二者相减即可。

#include #include #include #include using namespace std;using LL = long long;LL mul(LL a, LL b, LL p) {    a %= p, b %= p;    LL c = (long double)a * b / p;    LL ans = a * b - c * p;    ans += (ans < 0) ? p : 0;    ans -= (ans >= p) ? p : 0;    return ans;}int main() {    LL a, b, p;    scanf("%lld%lld%lld", &a, &b, &p);    printf("%lld\n", mul(a, b, p));}

最短 \(\text{Hamilton}\) 路径 (\(\texttt{ACW91}\))

给定一张 \(n\) 个点的带权无向图，点从 \(0∼n−1\) 标号，求起点 \(0\) 到终点 \(n−1\) 的最短 \(\text{Hamilton}\) 路径。

\(\text{Hamilton}\) 路径的定义是从 \(0\) 到 \(n−1\) 不重不漏地经过每个点恰好一次。 \(n \leq 20\)。

考虑状态压缩 \(dp\)。由于 \(n\) 的规模很小，可以直接用二进制枚举每个点的状态，其中 \(1\) 表示经过一次，\(0\) 表示没有经过。

设置状态 \(f_{i, j}\) ，表示当前在第 \(i\) 个点，当前状态是 \(j\) 的最短路径。首先要枚举所有可行状态，刷表时枚举当前点和要走到的点，如果当前点没有被走到过或者要去的点已经走过一遍了，那么直接剪掉。最终答案即为 \(f_{n - 1, 2^n - 1}\)。

由此来看，复杂度为 \(O(2 ^ n n ^ 2)\)，但是剪枝强度很大，可以跑过。

#include #include #include #include using namespace std;const int N = 21;int f[N][1 << N];int n, w[N][N];int main() {    scanf("%d", &n);    for (int i = 0; i < n; i ++ )        for (int j = 0; j < n; j ++ )            scanf("%d", &w[i][j]);    memset(f, 0x3f, sizeof f);    f[0][1 << 0] = 0;    for (int i = 1; i < 1 << n; i ++ )        for (int j = 0; j < n; j ++ ) if (i & (1 << j)) {            for (int k = 0; k < n; k ++ ) {                if (i & (1 << k)) continue;                f[k][i | (1 << k)] = min(f[k][i | (1 << k)], f[j][i] + w[j][k]);            }        }    printf("%d\n", f[n - 1][(1 << n) - 1]);    return 0;}

起床困难综合征 (\(\texttt{ACW998}\))

本题思路是按位贪心。可以参照 \(01trie\) 进行理解。

形象地看，假设我有一个 \(n\) 位的二进制数，每一位都是 \(0\)，现在我可以把某一位变成一使得这个数最大，那么我肯定要变 \(n - 1\) 位，因为我只要把最高位设成 \(1\)，就会比 \(0 \sim n - 2\) 位都设成 \(1\) 要大 \(1\)。

本题也可以用这种思路，将答案从高位到低位按最优方案填充即可。

#include #include #include #include using namespace std;const int N = 100010;int n, m, w[N];string str[N];int calc(int bit, int now) {    for (int i = 1; i <= n; i ++ ) {        int x = w[i] >> bit & 1;        if (str[i] == "AND") now &= x;        else if (str[i] == "OR") now |= x;        else now ^= x;    }    return now;}int main() {    ios::sync_with_stdio(false);    cin.tie(nullptr), cout.tie(nullptr);        cin >> n >> m;    for (int i = 1; i <= n; i ++ )        cin >> str[i] >> w[i];        int val = 0, ans = 0;    for (int i = 29; ~i; i -- ) {        int res0 = calc(i, 0);        int res1 = calc(i, 1);        if (val + (1 << i) <= m && res0 < res1)            val += 1 << i, ans += res1 << i;        else ans += res0 << i;    }    cout << ans << endl;        return 0;}

关键词：因此可以二进制数时间复杂度