位运算
与、或、非、异或
x&&y、x||y、!x、x^y
补码
1+1111111..11=000000000000..00
2+1111111..10=000000000000..00
x+?=000000000000..00
x就是补码，,即~x+1就是一个数的补码
memset函数，把每个字节初始化
经验化的初始化为正无穷方法 memset(h,0x3f,sizeof h);
0x3f3f3f3f+0x3f3f3f3f不会溢出。
快速幂
7的二进制 表示 111
二进制表示是11110100001001000000
只需要计算、
、
、
、
、
、.....
.
就是说可以表示100000000。
计算量级别
代码：
int qpow(int a, int n){
int ans = 1;
while(n){
if(n&1) //如果n的当前末位为1
ans *= a; //ans乘上当前的a
a *= a; //a自乘
n >>= 1; //n往右移一位
}
return ans;
}
acwing 89题 a^b
求 a 的 b 次方对 p 取模的值。
输入格式
三个整数 a,b,p ,在同一行用空格隔开。
输出格式
输出一个整数，表示a^b mod p的值。
数据范围
数据保证 p≠0
输入样例：
3 2 7
输出样例：
2
数据量分析：
a、b、p都是int范围之内，但是在计算快速幂的过程中，存在a*a的操作，所以会爆int范围。需要注意
特殊样例1：(爆int)
126348976 982638476 938420413
会超出int的表示范围
通过，避免了溢出的问题，*1ll把变量变为long long类型。注意
不会起作用，因为
会先计算，此时已经爆了。
特殊样例2：（b=0）
123456789 0 1
cout<<res%p<<endl; 此时的取模是有必要的。
此时的b等于0，所以根本不会进入while循环，最后结果会是1，但是因为p是1，所以需要再取模一次，结果为0
代码如下：
#include<iostream>
using namespace std;
int a,b,p;
int main()
{
cin>>a>>b>>p;
int res=1;
while(b)
{
if(b&1)
res=(res*1ll*a)%p;
a=(a*1ll*a)%p;
b>>=1;
}
cout<<res%p<<endl;
return 0;
}
acwing 90题 64位整数乘法
求 a 乘 b 对 p 取模的值。
输入格式
第一行输入整数a，第二行输入整数b，第三行输入整数p。
输出格式
输出一个整数，表示a*b mod p的值。
数据范围
输入样例：
3
4
5
输出样例：
2
数据量分析：
a、b、c都是范围内的数，
做乘法会超过64位数表示范围。
int是32位，范围是
long long 是64位，范围是次方，做加法不会超，乘法会超。
如计算，7对应111，就是计算
;
代码如下：
#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;
a=a*2%p;
}
cout<<res<<endl;
return 0;
}
acwing 91题 最短Hamilton路径
给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数n。
接下来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]。
输出格式
输出一个整数，表示最短Hamilton路径的长度。
数据范围
输入样例：
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
题目分析：
从起点0到n-1终点的最短路径
0 1 2 3 4 ......
我们来看一下 假设0->1->2->3的路径长度是20，0->2>1>3的路径长度是 12，那么接下来，到4甚至更多的时候，0->1->2->3就不可能是最短路径里面的一部分，所以我们可以用两个变量存储一下结果
i变量，当前遍历了哪些点，j变量当前停在哪个点。
用存储所有的可能。
表示当前遍历了i里面为1的节点，j表示当前在j，从k转移到j。
i-(1<<j)表示当前遍历了i里面为1的除了j的节点
状态转移方程：
数据量分析
N最大是20，如果不做上面的状态压缩，那么总共有种状态，第一个点有19种选择，第二个点有18种选择，第三个点有17中选择......
作了上述状态压缩，总共有。
表示停在j点，然后我们用i的第k位表示我们遍历了第k个点了没有，1表示遍历了，0表示没有。
初始状态，我们起点是0，即当前在0，j=0，所以就是第0位为1，其余为为0，i就等于1，。
时间复杂度为状态数乘以k的个数。
最终结果为终点为n-1，同时点都遍历了，就是全1了，即。
代码如下：
#include<iostream>
#include<cstring>
using namespace std;
const int N=20;
int arr[N][N],f[1<<N][N];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>arr[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>>j&1)//当前在j
{
for(int k=0;k<n;k++)
{
if(i-(1<<j)>>k&1)//去掉j,表示我们从哪个状态过来的。
f[i][j]=min(f[i-(1<<j)][k]+arr[k][j],f[i][j]);
}
}
}
}
cout<<f[(1<<n)-1][n-1]<<endl;
return 0;
}
附录：
异或操作实现配偶
0 1
2 3
4 5
6 7
，
，
，
，
互相配对。
在图论中有作用，正向边和反向边，可以通过异或操作直接得到某正向边的反向边。lowbit运算
lowbit(11110001000) 得到1000
(~n+1)&n也就是-n&n
