memset只能赋值出“每8位都相同”的int
0x7F7F7F7F是memset能初始化出的最大数组，但需要将一个数组中的数组初始化为正无穷时，为了避免加法运算上溢或者繁琐判断，一般用0x3F3F3F3F
1
<
<
n
=
2
n
1<
“整数/2”在c++实现为“除以2向零取整”，比如(-3)/2=-1
a b m o d p a^b\mod p abmodp
0
≤
a
,
b
≤
1
0
9
0≤a,b≤10^9
0≤a,b≤109
1
≤
p
≤
1
0
9
1≤p≤10^9
1≤p≤109
b = c k − 1 ∗ 2 k − 1 + c k − 2 ∗ 2 k − 2 + . . . + c 0 ∗ 2 0 b=c_{k-1}*2^{k-1}+c_{k-2}*2^{k-2}+...+c_0*2^0 b=ck−1∗2k−1+ck−2∗2k−2+...+c0∗20
a b = a c k − 1 ∗ 2 k − 1 ∗ a c k − 2 ∗ 2 k − 2 ∗ . . . ∗ a c 0 ∗ 2 0 a^b=a^{c_{k-1}*2^{k-1}}*a^{c_{k-2}*2^{k-2}}*...*a^{c_0*2^0} ab=ack−1∗2k−1∗ack−2∗2k−2∗...∗ac0∗20
且 a 2 i = a 2 i − 1 ∗ 2 = ( a 2 i − 1 ) 2 a^{2^i}=a^{2^{i-1}*2}=(a^{2^{i-1}})^2 a2i=a2i−1∗2=(a2i−1)2因此遍历b的每一位，如果当前这位是1，说明要乘上这个系数，而这个系数是随着遍历b的每一位，每次变成自己的平方
#include ll ans = 1 % p，初始化ans也要取模，否则可能b为0且p为1时，答案错误1 ≤ a , b , p ≤ 1 0 18 1≤a,b,p≤10^{18} 1≤a,b,p≤1018
将b化为二进制表示后， a ∗ b = c k − 1 ∗ a ∗ 2 k − 1 + c k − 2 ∗ a ∗ 2 k − 2 + . . . + c 0 ∗ a ∗ 2 0 a*b=c_{k-1}*a*2^{k-1}+c_{k-2}*a*2^{k-2}+...+c_0*a*2^0 a∗b=ck−1∗a∗2k−1+ck−2∗a∗2k−2+...+c0∗a∗20
又因为 a ∗ 2 i = ( a ∗ 2 i − 1 ) ∗ 2 a*2^i=(a*2^{i-1})*2 a∗2i=(a∗2i−1)∗2
发现运算过程中每一步的结果都不超过 2 ∗ 1 0 18 2*10^{18} 2∗1018，仍然在64位整数longlong的表示范围内
#include n xor (1 << k)（结论：1、异或0不会产生变化；2、异或1会取反）n | (1 << k)n & (~(1 << k))（注意如何由1表示0，取反）n & ((1 << k) - 1)（让前面的位都是0，因此&0，让后面的位原先是1的为1，原先是0的为0，因此&1）ans += (res0 << bit)（不需要分类讨论为res0是0还是1）题意：
思路：
#include 题意 ：
思路 ：
#include lowbit(n)定义为 非负整数n（即
n
>
0
n>0
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 ：
#include lowbit运算也是树状数组（0x42）中的一个基本运算
以已知的“问题边界”为起点向“原问题”正向推到的扩展方式就是 递推
题意 ：
思路 ：
void dfs(int u, int state) {
if (u == n) {
for (int i = 0; i < n; ++ i) {
if (state >> i & 1)
cout << i + 1 << ' ';
}
cout << endl;
return ;
}
dfs(u + 1, state + (1 << u));
dfs(u + 1, state);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
dfs(0, 0);
}
题意 ：
思路 ：
剪枝后时间复杂度从
2
n
2^n
2n降为
C
n
m
C^m_n
Cnm，剪枝：表示已选元素容器的vector如果size大于m或者加上剩下所有的数仍然小于m，则return剪枝int n, m;
void dfs(int u, int s, int state) {
if (s == m) {
for (int i = 0; i < n; ++ i)
if (state >> i & 1)
cout << i + 1 << ' ';
cout << endl;
return ;
}
if (u == n) return ;
for (int i = u; i < n; ++ i) {
dfs(i + 1, s + 1, state + (1 << i));
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
dfs(0, 0, 0);
}
题意 ：
思路 ：
int n;
vector<int> path;
void dfs(int u, int state) {
if (u == n) {
for (int i = 0; i < path.size(); ++ i)
cout << path[i] + 1 << ' ';
cout << endl;
return ;
}
for (int i = 0; i < n; ++ i) {
if (!(state >> i & 1)) {
path.push_back(i);
dfs(u + 1, state + (1 << i));
path.pop_back();
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
dfs(0, 0);
}
题意 ：
思路 ：
#include 题意 ：
思路 ：
#include 题意 ：
思路 ：
#include 题意 ：
思路 ：
#include 对于一个给定的数列A，它的差分数列B定义为：
B
[
1
]
=
A
[
1
]
,
B
[
i
]
=
A
[
i
]
−
A
[
i
−
1
]
(
2
≤
i
≤
n
)
B[1]=A[1],B[i]=A[i]-A[i-1](2 \leq i \leq n)
B[1]=A[1],B[i]=A[i]−A[i−1](2≤i≤n)
差分序列B的前缀和序列就是原序列A，前缀和序列S的差分序列也是原序列A
把序列A的区间[l, r]加上d，其差分序列B的变化为 B l + d , B r + 1 − d B_l+d,B_{r+1}-d Bl+d,Br+1−d，其他位置不变
差分序列与原序列共用一个数组：for (int i = n; i; i -- ) a[i] -= a[i - 1];（原序列下标从1开始）
题意 ：
思路 ：
#include 题意 ：
思路 ：
#include