前置知识

一些约定

1.在m位的二进制数中，为方便起见，称最低位为0，最高位为m-1。

2.“运算补位”对于任意两个二进制数的位运算（与 或 非 异或）分别用n和m表示其位数，若参与位运算的两个二进制数位数不统一（n<m）或(n>m)则可以看作用0补全位数低的那个二进制数使其位数一样参与运算。（例如11010 & 1可以看作11010 & 00001）（即对于二进制数1来说除了第0位其他数位均未使用，默认为0）。

按位与运算【and】【&】

若同位数字都为1则为1，有一个不为1则为0。

例：

10110
& 11010
---------
10010

因此我们拥有非常显而易见的性质：

1 & 1 = 1

0 & 1 = 0

1 & 0 = 0

0 & 0 = 0

我们从上方的性质可知：\
对于二进制数的每一位，若我们让这一位 & 1，结果仍然是这位二进制数；若我们让其 & 0那么这一位肯定为0。

按位或运算【or】【|】

相同位只要有1个为1那么就为1。
例：

10110
| 11010
---------
11110
因此我们拥有非常显而易见的性质：

1 | 1 = 1

0 | 1 = 1

1 | 0 = 1

0 | 0 = 0

那么从上方性质可知：

对于二进制数的每一位，若使其 or 1则这一位一定是1；若使其 or 0则这一位二进制数仍为原来这个数位上的数。

按位非（取反）运算【not】【~】

即将一个二进制数取反。

~1 = 0

~0 = 1

按位异或运算 【xor】【^】

对于两个二进制数A，B的第i位，若\(A_i\) \(=\) \(B_i\) 则为0， \(A_i\) \(≠\) \(B_i\)则为1。

1 ^ 1 = 0

0 ^ 1 = 1

1 ^ 0 = 1

0 ^ 0 = 0

我们可以观察到任何数异或1都为其取反的结果。

补码

作用：能够使用二进制表示负数

例如：

1 + ？ =0000 0000 0000

？ = 1111 1111 1111 1111

2 + ？ = 0

？ = 1111 1111 1111 11110

x + ？ = 0

？ = ~x+1

即对于x而言，x的补码为~x+1。

即 -x = ~x+1

位移运算（<<） (>>)

左移：在二进制表示下把数字同时向左移动，低位以0补充。

例如：\(0001 << 1\) \(=\) \(0010\)

那么我们对于一个十进制整数a进行左移x位操作，结果为c，即\(a << x\) = \(c\)

那么十进制整数\(c=?\)

根据数学常识以及二进制的定义，十进制数a一定可以分解成若干个指数不重复的2的次幂的和。如果十进制数a的二进制数一共有k位（k），每位为\(b_i\)那么：

\(a = b_02^0+b_12^1+b_22^2+....b_{k-2}2^{k-2}+b_{k-1}2^{k-1}\)
即
\( a = \sum_{i=0}^{k-1}b_i2^i \)

设 a << x = c，\(d_j\)表示其二进制状态下的每一位，则有：

\( c = \sum_{j=x}^{k-1+x}d_j2^j \)
我们可以通过移位前的二进制数位i+x来找到i移位后的x数位，也就是说对于每个\(b_i\)，我们都可以找到一个\(d_j\)使得\(b_i = d_j\)，其中\(j = i + x\)。那么相应的每组\(b_i2^i\)也有所对应的\(d_j2^j\)即\(d_{i+x}2^{i+x}\)。其中\(b_i=d_{i+x}\)，\(2^{i+x} = 2^i*2^x\)，即每个\(b_i2^i\)随对应的\(d_j2^j\)为\(b_i2^{i+x} = b_i * 2^i * 2 ^ i\)
因此
\( \sum_{i=x}^{k-1+x}d_j2^j = \sum_{i=0}^{k-1}b_i2^i2^x \)
即\(a << x = 2^xa\)

算术右移：二进制补码表示下把数字同时向右移动，搞伪以符号位补充，低位越界后舍弃。

例如：\(1000 >> 1\) \(=\) \(0100\)

同样地，对于一个十进制整数\(a >> x\)相当于\(a/2^x\)。
证明：
\(a = b_02^0+b_12^1+b_22^2+....b_{k-2}2^{k-2}+b_{k-1}2^{k-1}\)
即
\( a = \sum_{i=0}^{k-1}b_i2^i \)

设 a >> x = c，\(d_j\)表示其二进制状态下的每一位，则有：

\( c = \sum_{j=0}^{k-x}d_j2^j \)
我们可以通过移位前的二进制数位i-x来找到i移位后的x数位，也就是说对于每个\(d_j\)，我们都可以找到一个\(b_i\)使得\(b_i = d_j\)，其中\(i = j + x\)。那么\(d_j2^j\)也有所对应的\(b_i2^i\)即\(d_{j+x}2^{j+x}\)。其中\(b_i=d_{j+x}\)，\(2^{j+x} = 2^i * 2^x\) 即每个\(d_j2^j\)所对应的\(b_i2^i\)为\(d_j*2^i*2^x\)
即
\( \sum_{i=0}^{k-1}b_i2^i = \sum_{i=0}^{k-x-1}b_i2^i2^x \)
即\(a = c * 2^x\) 那么\(c = a/2^x\)

lowbit()运算

lowbit(n)表示为非负整数n在二进制表示下“最低位的1”是多少。
例如对于 n = 10 \(lowbit(10)_{10} = lowbit(1010)_{2}=(10)_{2}=2\)

公式推导：

设 n > 0, n 的第k位是1，第0~k-1位都是0.
我们把n取反，此时第k位为0，第0~k位为1.那么我们令n = n+1，因为进位第k位为1，第0~k-1位为0。而在取反加一操作后，n的第k+1到最高位恰好与原来相反，所以\(n\) & \((\) ~\(n+1)\)后只有第k位为1，其余都为0，由于补码的性质 即
-n = ~n+1

那么

\(lowbit(n) = n\) & \((\) ~\(n+1)\) = \(n\) & \((-n)\)

状态压缩

二进制状态压缩，是将一个长度为m的bool数组用一个m位二进制整数表示存储的方法。可以利用如下的方法实现原bool数组对应下表的存取。

操作 | 运算 |

-|-|
取出整数n在二进制表示下第k位| (n >> k) & 1 |
取出整数n在二进制表示下第0~k-1位（后k位）|n & ((1<<k)-1) （即将后k位全都设为1并用n进行与运算）|
把整数n在二进制表示状态下的第k位取反| n^(1<<k)|
把整数n在二进制表示下的第k为赋值1| n or (1<<k)|
对整数n在二进制表示下的第k位赋值为0 |n &(~(1<<k))

例题

a ^ b （快速幂）

求 a 的 b 次方对 p 取模的值。

输入格式

三个整数 a,b,p ,在同一行用空格隔开。

输出格式

输出一个整数，表示a^b mod p的值。

数据范围

0≤a,b,p≤109

输入样例：

3 2 7

输出样例：

2

同样地，对于每个b，我们可以表示为（整数b的二进制形式有k位）。
\(b = c_02^0+c_12^1+c_22^2+....c_{k-2}2^{k-2}+c_{k-1}2^{k-1}\)

即
\( b = \sum_{i=0}^{k-1}c_i2^i \)

那么对于

\(a^b =a^{\sum_{i=0}^{k-1}c_i2^i} =a^{c_02^0+c_12^1+c_22^2+....c_{k-2}2^{k-2}+c_{k-1}2^{k-1}}= a^{c_k-1*2{k-1}}*a^{c_k-2*2{k-2}}*a^{c_k-3*2{k-3}}......a^{c_0+2^0}\)

因为 \(k\) = \(\lceil log_2(b+1)\rceil\)（向上取整，即对于整数b的二进制位数）

所以上述乘积项的项数不多于\(\lceil log_2(b+1)\rceil\)个，复杂度为\(O(log_2 b)\)。

而我们本质上要求的就是若干个\(a^{2^i}\)相乘的结果。

又因为

\(a^{2^i} = (a^{2^{i-1}})^2\)

那么我们只需要k次递推求出每次的乘积项，当\(c_i\) = 1时，即二进制位为1的时候将乘积累积到答案中。我们可以用b & 1运算表示b的二进制下的最低位，并用b >> 1来舍去最低位。

int ans = 1;
    for (;b;b >>= 1){
        if (b & 1){
            ans = 1ll * ans * a;//通过乘上1ll进行类型转换
        }
        a = 1ll * a * a;
    }

而根据取模的性质

(a + b) % p = (a % p + b % p) % p （1）

(a - b) % p = (a % p - b % p) % p （2）

(a * b) % p = (a % p * b % p) % p （3）

a ^ b % p = ((a % p)^b) % p （4）

即(a * b)% p = (a % p * b % p ) % p

我们可以让 ans,a分别%p

#include <iostream>
using namespace std;

int main(){
    int a,b,p;
    cin >> a >> b >> p;
    int ans = 1 % p;
    for (;b;b >>= 1){
        if (b & 1){
            ans = 1ll * ans * a % p;
        }
        a = 1ll * a * a %p;
        cout << ans << " ";
    }
    cout << ans;
}

64位整数乘法

求 a 乘 b 对 p 取模的值。

输入格式

第一行输入整数a，第二行输入整数b，第三行输入整数p。

输出格式

输出一个整数，表示a*b mod p的值。

数据范围

\[ 1≤a,b,p≤ 10^{18}\]

输入样例：

3
4
5

输出样例：

2

很显然，\(10^{18} * 10^{18}\)已经超出了c++可存整数范围的，我们不可以通过直接相乘取模，那么根据二进制的“倍增”思想，我们按下拆分。

对于

\(a * b = a * (\sum_{i=0}^{k-1}c_i2^i)\)
同理，有\(a * 2^i = a * 2^{i-1} * 2\) 根据取模的性质

(a + b) % p = (a % p + b % p) % p

对于\(a * 2^{i-1} * 2 mod p\) 运算过程的每一步都不会超过\(2*10^{18}\),完全在可接受的范围内。那么为什么运算过程的每一步都不会超过\(2*10^{18}\)呢？

首先，a是一个不超过\(10^{18}\)的正整数，而p也为不超过不超过\(10^{18}\)的正整数，也就是说如果a经过*2操作之后超过了\(10^{18}\)那么经过取模之后则为一个较小的数，而这样取模是符合取模的性质的。而整个操作中所产生最大的数即a为\(10^{18}\)乘2后为\(2 * 10^{18}\)

#include <iostream>
using namespace std;

int main(){
    long long a,b,p,ans;
    cin >> a >> b >> p;
    for (;b; b >>= 1){
        if (b & 1){
            ans = (ans + a) % p;
        }
        a = a*2 % p;
    }
    cout << ans;
}

快递员秋葵的烦恼 （状压DP）~~状压杀我呜呜呜~~

杜王町为了使居民串门方便进行了新一轮的城镇规划，在新一轮规划之后每两户都存在一条路径。而秋葵是杜王町的一个邮递员，每一天都要给每户送信，而每户所收的信为一封，秋葵如何送信才能使得所经过的路径最短呢？

输入格式
第一行输入一个整数n。

接下来n个整数，其中第i行第j个整数表示点i到点j的距离（记为a[i,j]）。

对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

输出格式
输出一个整数，表示最短路径的长度。

数据范围

1≤n≤20

0≤a[i,j]≤107

输入样例：

5

0 2 4 5 1

2 0 6 5 3

4 6 0 8 3

5 5 8 0 5

1 3 3 5 0

输出样例：

18

如果考虑DP的话，那么应该如何划分状态？
首先需要确定我们要考虑的因素，因为Hamiton路径每个点只能经过一次，并且要经过所有的点，所以我们应该考虑当前的状态经过哪些点，但是如果只考虑当前经过哪些点的话，我们没有办法确定当前的最短路径是多少，即我们不知道我们是从哪个点转移过来的，那么我们就需要考虑我们当前所在的是哪个点，那么我们就可以知道我们从哪里转移过来，边权是多少，我们就可以更新我们的最短路。

我们需要考虑的因素：

1.当前经过哪些点

2.当前在那哪个点

那么我们就应该考虑状态：

我们用\(f[i][j]\)表示当前的状态，其中i是当前所经过点的集合，j是当前所在的点。

考虑完状态之后我们就需要考虑如何转移：

因为每两个点之间都存在路径，所以我们可以从任意一个点转移过来，但是我们要确保向当前状态转移的状态的当前状态点没有访问且访问了向当前状态转移的状态的点。

即：

\(f[i][j] = min([state_k][k]+w[k][j],f[i][j])\)

其中\(state_k\) \(j\)未被访问，且包括\(k\)这个点。

换言之就是\(state_k\)为集合\(i\)中\(j\)未被访问，但\(k\)被访问的集合，这样就与当前状态建立了联系。

那么我们首先可以枚举集合\(i\),即枚举通过的点来扩展状态。

接下来我们可以通过枚举合法的\(j\)与合法的\(k\)来确定状态的最优解。

\(j\)合法：即\(i\)集合中包括\(j\)。

\(k\)合法：即\(i\)集合中\(k\)已被访问。

那么我们用什么来确定每个点是否被访问？

因为数据规模比较小，所以我们可以用一个32位二进制整数n的第i位来保存第i个点是否被访问。

---

那么我们就可以得到完整的状态转移方程：

\(f[i][j] = min(f[i xor(1<<j)][k] + w[k][j],f[i][j])\)

且满足于\((i >> j) \) & \( 1 = 1\)

\((i xor(1<<j)) >> k\) & \(1 = 1\)

---

其中，\((i >> j) \) & \( 1 = 1\)（是确保当前状态下i的第\(j\)位一定为1，即\(j\)点被访问。

而 \(i xor(1<<j)\)则代表将\(i\)的第\(j\)位取反 即在\(i\)中\(j\)未被访问（其余不变）的状态。

其复杂度为\(O(2^n*n)\)

#include <iostream>
#include <cstring>
using namespace std;
int f[1 << 20][25],w[25][25],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;
    for (int i = 0; i <= 1 << n; i++){
        for (int j = 0; j < n; j++){
            if (i&(1<<j) == 1 << j){
                for (int k = 0; k < n; k++){
                    if ((i^1<<j) >> k & 1){
                        f[i][j] = min(f[i][j],f[i^1<<j][k] + w[k][j]);
                    }
                }
            }
        }
    }
    cout << f[(1<<n)-1][n - 1];
    return 0;
}