#1 位运算

学习资料

代码实现

快速幂

快速幂思想转化

将指数 y 表示为二进制的形式，易证：

将 $3^9$ 的指数 $9$ 表示为 $(1001)_2$

则 $3^9 = 3^1 * 3^8 = 1 * 3^{2^0} * 0 * 3^{2^1} * 0 * 3^{2^2} * 1* 3^{2^3}$

所以用倍增思想预处理出来 $3^1 ,3^2 ,3^4 ,3^8$ 即 $3^{2^0}, 3^{2^1} ,3^{2^2} ,3^{2^3}$

再按照二进制位 有一则乘 即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,b,p;
LL ksm(LL x, LL y, LL z){ // 二进制思想
    LL res = 1;
    while(y){
        if(y & 1) res = res *x %z; // 当 指数 在二进制下为一时
        x = x*x %z; // 预处理 x 的值
        y /= 2; // 处理下一个二进制位
    }
    return res %z; //注意取模
}
int main(){
    scanf("%lld%lld%lld",&a,&b,&p);  //要用 long long
    printf("%lld",ksm(a, b, p));
}

扩展延伸—状压DP

例题

代码

思路与上一题类似

$ a * b = \sum_{i=1}^ba = a + a +…+a$

用二进制表示的话

$a * 1 = a = a * 2^0$
$a * 2 = 2a = a * 2^1$
$a * 4 = 4a = a * 2^2$
$……$
$a * 2^k = 2^ka$

预处理所有值，有一则加即可

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
ULL a, b, p;

ULL cf64(ULL x,ULL y,ULL z){ 
    ULL res = 0; //记得清零
    while(y){
        if(y & 1) res = (res + x) %z;
        y /= 2;
        x = x * 2 %z;
    }
    return res %z;
}

int main(){
    scanf("%lu %lu %lu",&a, &b, &p);

    printf("%lu", cf64(a, b, p));
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20, state = 1 << N;

int n;
int f[state][N]; 
// 二进制表示第 i 位为 1/0 表示是/否经过了点 i
// f[state][j] 从 0 经过所有 state 包含的点，
// 且当前到达了点 j 上的所有路径
int w[N][N];
// 存边上的距离
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; 
    // 二进制表示中经过点集为 1 的 0 号点走过的点是 0

    for (int i = 0; i < 1 << n; i ++ ) 
    // 从 0 到 111...11 枚举是否到达 state 包含的点 
        for (int j = 0; j < n; j ++ )  
        // 枚举当前 state 到达的点
            if (i >> j & 1) {  
                // 如果当前点集包含点 j，那么进行状态转移
                for (int k = 0; k < n; k ++ ) // 枚举所有 k
                    if (i - (1 << j) >> k & 1) {
                // 如果从当前状态经过点集 state 中，去掉点 j 后
                // state 仍然包含点 k，那么才能从点 k 转移到点 j
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                    }
            }

    cout << f[(1 << n) - 1][n - 1] << endl;
    // 最后输出 f[111...11][n-1]
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

int n, m;  // n, m 即题目描述中 n, m
int ans;   // ans 存我们能造成的最大的伤害

int t [100010]; // t 存输入的 n 个数
int op[100010]; // op 存 n 个数对应的操作，
    //1 表示按位或，2 表示按位异或，3 表示与
char sr[4];
int ha[26]; // hash 表

bool cale(bool x, int g) { // x 是经过所有操作的第 g 位后的结果
    for(int i = 1; i <= n; i ++) {
        // 从 0 到 n 枚举所有读入的数与其对应操作
        if(op[i] == 1) x |= t[i] >> g & 1; // 按位或
        if(op[i] == 2) x ^= t[i] >> g & 1; // 按位异或
        if(op[i] == 3) x &= t[i] >> g & 1; // 按位与
    }
    return x; // 还回第 g 位的结果
}
int main(){
    ha['O'-'A']=1,ha['X'-'A']=2,ha['A'-'A']=3; // hash 表
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i ++) {

        scanf("%s %d", sr, &t[i]);
        op[i] = ha[sr[0] - 'A'];
    }

    for(int i = 30; i >= 0; i --) {
        if(m >> i){
        // 如果说 m 右移 i 位仍不为 0，说明该位填 1 后小于 m，
            bool x = cale(0, i), y = cale(1, i); 
            // 分别处理出该位填 0 的结果和该位填 1 的结果

            if(x >= y) // 如果该位填 1 并不比该位填 0 更优
                ans |= x << i;
            // 那么为了让剩下能填的数更大，在该位填 0

            else{ // 否则在该位填 1
                ans |= y << i; 
                m -= y << i;//填完后让 m 减去该位填 1 的结果
        //这样在后面填数的时候只用考虑是否大于 m - 1 就可以了
            }
        }
        else ans |= cale(0, i) << i; // 否则该位只能填 0
    }

    printf("%d", ans);
}