基本运算
| 运算 | C++ 符号 | 意义 |
|---|---|---|
and |
& |
按位与 |
or |
| |
按位或 |
not |
~ |
按位取反 |
xor |
^ |
按位异或 |
shl |
<< |
左移 |
shr |
>> |
右移 |
注意运算符运算顺序优先级，可参考 https://www.cnblogs.com/greyqz/p/operator.html。
技♂巧
（源：江苏省淮阴中学薛志坚）
| 功能 | 示例 | 位运算 |
|---|---|---|
| 去掉最后一位 | (101101 -> 10110) | x >> 1 |
| 在最后加一个 0 | (101101 -> 1011010) | x << 1 |
| 在最后加一个 1 | (101101 -> 1011011) | x << 1 + 1 |
| 把最后一位变成 1 | (101100 -> 101101) | x | 1 |
| 把最后一位变成 0 | (101101 -> 101100) | x | 1 - 1 |
| 最后一位取反 | (101101 -> 101100) | x ^ 1 |
| 把右数第 k 位变成1 | (101001 -> 101101, k = 3) | x | (1 << (k - 1)) |
| 把右数第 k 位变成0 | (101101 -> 101001, k = 3) | x & !(1 << (k - 1)) |
| 右数第 k 位取反 | (101001 -> 101101, k = 3) | x ^ (1 << (k - 1)) |
| 取末 k 位 | (1101101 -> 1101, k = 5) | x & (1 << k - 1) |
| 取右数第 k 位 | (1101101 -> 1, k = 4) | x << (k - 1) & 1 |
| 把末 k 位变成 1 | (101001 -> 101111, k = 4) | x | (1 << k - 1) |
| 末 k 位取反 | (101001 -> 100110,k = 4) | x ^ (1 << k - 1) |
| 把右边连续的 1 变成 0 | (100101111 -> 100100000) | x & (x + 1) |
| 把右起第一个 0 变成 1 | (100101111 -> 100111111) | x | (x + 1) |
| 把右边连续的 0 变成 1 | (11011000 -> 11011111) | x | (x - 1) |
| 取右边连续的 1 | (100101111 -> 1111) | (x ^ (x + 1)) << 1 |
| 去掉右起第一个 1 的左边 | (100101000 -> 1000) | x & !(x ^ (x - 1))（或 x & (-x)） |
判断一个数 x 是否是 2 的整数次幂：
if (!(x&x-1)) // 法 1
if ((x&-x)==x) // 法 2
Quick swap
a ^= b; b ^= a; a ^= b;
Quick min
inline int min(int a, int b) {
int c = (a - b) >> 31;
return a ^ c | b ^ ~c;
}
lowbit
[operatorname{lowbit}(n)=n ~&~ (sim n+1)=n~&~(-n)
]
popcount
统计 1 的个数：
for (; x; x-=x&-x) ++cnt;
统计 0 的个数：
for (; x; x&=x-1) ++cnt;
统计 32 位无符号整数中 1 的个数：
inline int popcount(unsigned int i) {
i=i-((i>>1)&0x55555555);
i=(i&0x33333333)+((i>>2)&0x33333333);
i=(i+(i>>4))&0x0f0f0f0f;
i=i+(i>>8);
i=i+(i>>16);
return i&0x3f;
}
Quick log (Hash)
令 (H[2^k mod 37]=k)。因为 (forall kin[0,35], 2^k mod 37) 互不相等，且恰好取遍整数 1~36。
int H[37];
for (int i=0; i<36; ++i) H[(1ll<<i)%37]=i;
Quick Power
#include <cstdio>
#define ll long long
int n, m, mod;
int qpow(int x, int y) {
int res=1%mod;
for (; y; x=(ll)x*x%mod, y>>=1) if (y&1) res=(ll)res*x%mod;
return res;
}
int main() {
scanf("%d%d%d", &n, &m, &mod);
printf("%d
", qpow(n, m));
return 0;
}
Quick Multiply
#include <cstdio>
#define ll long long
ll n, m, mod;
ll qmul(ll x, ll y) {
ll res=0;
for (; y; x=(x<<1)%mod, y>>=1) if (y&1) res=(res+x)%mod;
return res;
}
int main() {
scanf("%lld%lld%lld", &n, &m, &mod);
printf("%lld
", qmul(n, m));
return 0;
}
shortest Hamilton path
Hamilton 路径：从 0 到 (n-1) 不重不漏地经过每个点恰好一次。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=20;
int n, dist[N][N], f[1<<N][N];
int main() {
scanf("%d", &n);
for (int i=0; i<n; i++) for (int j=0; j<n; j++)
scanf("%d", &dist[i][j]);
memset(f, 0x3f, sizeof f);
f[1][0]=0;
for (int i=1; i<1<<n; i++)
for (int j=0; j<n; j++) if (i>>j&1)
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]+dist[k][j]);
printf("%d
", f[(1<<n)-1][n-1]);
return 0;
}
状态压缩动态规划
[SCOI2005] 互不侵犯
在 N×N 的棋盘里面放 K 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 8 个格子。
// p1896
#include <cstdio>
#define ll long long
using namespace std;
const int N = 11, M = 2000;
int n, m;
ll ans, dp[N][M][N*N];
int s[M], t[M], cnt;
void dfs(int x, int stat, int p) {
if (x >= n) {
s[++cnt] = stat, t[cnt] = p;
return;
}
dfs(x+1, stat, p);
dfs(x+2, stat|(1<<x), p+1);
}
int main() {
scanf("%d%d", &n, &m);
dfs(0, 0, 0);
for (int i=1; i<=cnt; i++) dp[1][i][t[i]]=1;
for (int i=2; i<=n; i++)
for (int j=1; j<=cnt; j++)
for (int k=1; k<=cnt; k++) {
if (s[j] & s[k]) continue;
if ((s[j]<<1) & s[k]) continue;
if (s[j] & (s[k]<<1)) continue;
for (int l=m; l>=t[j]; l--)
dp[i][j][l] += dp[i-1][k][l-t[j]];
}
for (int i=1; i<=cnt; i++) ans += dp[n][i][m];
printf("%lld
", ans);
return 0;
}
[USACO06NOV] Corn Fields
农场主 John 新买了一块长方形的新牧场，这块牧场被划分成 M 行 N 列 (1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John 打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是 John 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。John 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
// p1879
#include <cstdio>
using namespace std;
const int N = 4197, M = 15, MOD = 100000000;
int n, m, dp[M][N], ans;
struct node { int s[N], st; } p[M];
int main() {
scanf("%d%d", &m, &n);
for (int i=1, a, t; i<=m; i++) {
t = 0;
for (int j=1; j<=n; j++)
scanf("%d", &a), t = (t<<1) + 1 - a;
for (int j=0; j< (1<<n); j++)
if ((j&(j<<1))||(j&(j>>1))||(j&t)) continue;
else p[i].s[++p[i].st] = j;
}
for (int i=1; i<=p[1].st; i++) dp[1][i] = 1;
for (int i=2; i<=m; i++)
for (int j=1; j<=p[i].st; j++)
for (int k=1; k<=p[i-1].st; k++)
if (!(p[i].s[j] & p[i-1].s[k]))
dp[i][j] += dp[i-1][k];
for (int i=1; i<=p[m].st; i++)
ans = (ans + dp[m][i]) % MOD;
printf("%d
", ans);
return 0;
}