补码

memset只能赋值出“每8位都相同”的int

0x7F7F7F7F是memset能初始化出的最大数组，但需要将一个数组中的数组初始化为正无穷时，为了避免加法运算上溢或者繁琐判断，一般用0x3F3F3F3F

移位运算

$1<<n=2^n$

“整数/2”在c++实现为“除以2向零取整”，比如(-3)/2=-1

AcWing 89. a^b

$a^b\mathrm{mod}p$

$0\le a,b\le 10^9$
$1\le p\le 10^9$

$b=c_{k-1}\ast 2^{k-1}+c_{k-2}\ast 2^{k-2}+...+c_0\ast 2^0$

$a^b=a^{c_{k-1}\ast 2^{k-1}}\ast a^{c_{k-2}\ast 2^{k-2}}\ast ...\ast a^{c_0\ast 2^0}$

且$a^{2^i}=a^{2^{i-1}\ast 2}=(a^{2^{i-1}}{)}^2$因此遍历b的每一位，如果当前这位是1，说明要乘上这个系数，而这个系数是随着遍历b的每一位，每次变成自己的平方

• 快速幂时间复杂度为$O(lo{g}_{2}b)$

#include 
#define endl '\n'
#define _(a) cout << #a << ": " << (a) << "    "
using namespace std;
typedef long long ll;

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

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 快速幂
• 注意 ll ans = 1 % p，初始化ans也要取模，否则可能b为0且p为1时，答案错误
• 如果参数都写int，记得在乘法运算的时候第一个乘法参数前面加上强制转化成long long

AcWing 90. 64位整数乘法

$1\le a,b,p\le 10^{18}$

将b化为二进制表示后，$a\ast b=c_{k-1}\ast a\ast 2^{k-1}+c_{k-2}\ast a\ast 2^{k-2}+...+c_0\ast a\ast 2^0$

又因为$a\ast 2^i=(a\ast 2^{i-1})\ast 2$

发现运算过程中每一步的结果都不超过$2\ast 10^{18}$，仍然在64位整数longlong的表示范围内

#include 
#define endl '\n'
#define _(a) cout << #a << ": " << (a) << "    "
using namespace std;
typedef long long ll;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二进制状态压缩

• $(1<<i)=2^i=$ 第$i$位是1 $=$ 1后面跟着$i$个0
• 将n的第k位取反：n xor (1 << k)（结论：1、异或0不会产生变化；2、异或1会取反）
• 将n的第k位赋值1: n | (1 << k)
• 将n的第k位赋值0:n & (~(1 << k))（注意如何由1表示0，取反）
• 取出n的后k位（第0～k-1位）：n & ((1 << k) - 1)（让前面的位都是0，因此&0，让后面的位原先是1的为1，原先是0的为0，因此&1）
• m位二进制整数，当m不太大时，可以直接使用一个整数类型存出；当m较大时，可以用若干个整数类型（int数组），也可以直接用stl中的bitset（第0x71节）
• ans的第bit位为res0：ans += (res0 << bit)（不需要分类讨论为res0是0还是1）

AcWing 91. 最短Hamilton路径

题意：

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

思路：

• 朴素做法：枚举n个点的全排列，计算路径长度取最小值，$O(n\ast n!)$
• 二进制状态压缩DP $O(n^2\ast 2^n)$：
• 在任意时刻表示哪些点已经被经过，哪些点没有被经过：用一个n位二进制数；在任意时刻还需要知道当前所处的位置，因此，$F[i,j](0\le i<2^n,0\le j<n)$表示点被经过的状态对应的二进制数为i，且目前处于点j时的最短路径
• 在起点时，有$F[1,0]=0$，将F数组其他的值设为无穷大；最终目标是$F[(1<<k)-1.n-1]$
• 在任何时刻，有$F[i,j]=min(F[i$ xor $(1<<j),k]+weight(k,j))$，其中，$0\le k<n$并且$((i>>j)$ $ $1)=1$，因为每个点只能被恰好经过一次，所以在上一时刻“被经过的点的状态”对应的二进制数的第j位应该赋值为0

#include 
#include 
#define endl '\n'
#define _(a) cout << #a << ": " << (a) << "    "
using namespace std;
typedef long long ll;
const int N = 20, M = 1 << 20;

int n;
int w[N][N];
int dp[M][N];

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < n; ++ j)
            cin >> w[i][j];
    
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for (int i = 1; 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] + w[k][j]);
                    }
                }
            }
        }
    }
    cout << dp[(1 << n) - 1][n - 1];
}

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
35

AcWing 998. 起床困难综合症

题意 ：

• 选择[0, m]之间的一个整数$x_0$，经过给定的n次位运算，使结果ans最大
• $n\le 10^5,m\le 10^9$

思路 ：

• 位运算的主要特点之一：在二进制表示下不进位；我们可以从高位（因为要最大）到低位，依次考虑$x_0$的每一位填0还是填1
• $x_0$的第k位应该填1，当且仅当同时满足下列两个条件：
  1、已经填好的更高位构成的数值加上 1 << k 以后不会超过m
  2、用每个参数的第k位参与位运算，

#include 
#define endl '\n'
#define _(a) cout << #a << ": " << (a) << "    "
using namespace std;
typedef long long ll;
typedef pair<string, int> psi;
const int N = 1e5 + 10;

int n, m;
psi a[N];

int calc(int bit, int now) {
    for (int i = 1; i <= n; ++ i) {
        string op = a[i].first;
        int x = (a[i].second >> bit & 1);
        if (op == "AND") now &= x;
        else if (op == "OR") now |= x;
        else now ^= x;
    }
    return now;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> a[i].first >> a[i].second;
    int ans = 0, val = 0;
    for (int bit = 29; bit >= 0; -- bit) {
        int res0 = calc(bit, 0);
        int res1 = calc(bit, 1);
        if (val + (1 << bit) <= m && res1 > res0) {
            val += (1 << bit);
            ans += (res1 << bit);
        } else {
            ans += (res0 << bit);
        }
    }
    cout << ans;
}

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
35
36
37
38
39
40

成对变换

• 对于非负整数n：
  当n为偶数时，n xor 1 等于 n + 1
  当n为奇数时，n xor 1 等于 n - 1
• 这个性质经常用于图论 邻接表 中边集的存出，无向边（双向边）图中，一对正反方向的边（在第0x13节讲

lowbit运算

lowbit(n)定义为 非负整数n（即$n>0$） 在二进制表示下“最低位的1及后边所有的0”所构成的数值

结论：lowbit(n) = n & (~n + 1) = n & (-n)

推导：
设n>0，n的第k位为1，第0～k-1为都是0
对n取反加一后，n的第k+1位到最高位恰好与原来相反，第0～k-1位仍然为0；即仅有第k位为1，其余位都是0；然后用原先的n & 取反加一后的n
在补码表示下，~n = -1 - n

找出整数二进制表示下所有是1的位（所花费时间与1的个数同级）（lowbit配合Hash）：不断把n赋值位n - lowbit(n)，直至n = 0 ：

• c++math库的log函数以e为底，且复杂度常数较大，因此我们预处理一个数组，通过hash方法代替log运算；当n较小（比如20）时，令$H[2^k]=k$
• 效率更高的方法：建立一个长度为37的数组H，令$H[2^k\mathrm{mod}37]=k$；使用的数学思想：
• $\forall k\in [0,35],2^k\mathrm{mod}37$互不相等，且恰好取遍整数1～36

#include 
#define endl '\n'
#define _(a) cout << #a << ": " << (a) << "    "
using namespace std;
typedef long long ll;

int H[37];

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    for (int i = 0; i < 36; ++ i) H[(1ll << i) % 37] = i;
    int n;
    while (cin >> n) {
        while (n > 0) {
            cout << H[(n & -n) % 37] << ' ';
            n -= (n & -n);
        }
        cout << endl;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

lowbit运算也是树状数组（0x42）中的一个基本运算