位运算

a^b

image-20210512223422917

非常经典的快速幂算法，总之就是非常6啊，话不多数直接上代码吧；

C++ 技巧： 使用 >>= 来完成二进制数字的移位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>

using namespace std;

int main(){
    long long a,b,p;
    cin >> a >> b >> p;
    int res = 1 % p;
    while(b){
        if(b&1) res = a * res % p;
        a = a * a % p;
        b >>= 1;
    }
    cout << res;
    return 0;
}

64位整数乘法

image-20210513082306793

a * b mod p 其实就是n个a相乘后模p，将b看做一个二进制数，从左往右分别是1，2，4，8… 具体看代码了，总之就是非常的妙啊！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>

using namespace std;
typedef unsigned long long ULL;
int main(){
    ULL a,b,p;
    cin >> a >> b >> p;
    ULL res=0;
    while(b){
        if(b&1) res = (res + a)%p;
        b >>= 1; // b的二进制往右边移动一位（妙！）
        a = a* 2% p; // 对应2进制的1，2，4，8，因为是对b进行2进制位运算的；
    }
    cout << res;
}

递归实现指数型枚举

image-20210601153219772

提示：

使用位运算进行状态压缩；

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
#include <iostream>
#include <string>

using namespace std;

int a;

void dfs(int u, int state) {
    if (u == a) {
        for (int i = 0; i < a; i++)
            if (state >> i & 1)
                cout << i + 1 << ' ';
        cout << endl;
        return;
    }
    dfs(u + 1, state);
    dfs(u + 1, state | 1 << u);

}


int main() {
    cin >> a;
    dfs(0, 0);
    return 0;
}

递归实现组合型枚举

image-20210601155607376

提示：

使用二进制进行状态压缩；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

using namespace std;

int n, m;

void dfs(int u, int sum, int state) {
    if (sum + n - u < m) return;
    if (sum == m) {
        for (int i = 0; i < n; i++)
            if (state >> i & 1)
                cout << i + 1 << ' ';
        cout << endl;
        return;
    }
    dfs(u + 1, sum + 1, state | 1 << u);
    dfs(u + 1, sum , state);
}

int main() {
    cin >> n >> m;
    dfs(0, 0, 0);
    return 0;
}