striving & singing
https://www.luogu.com.cn/problem/P2467
若高度为 j 的位置和高度为 j - 1 的位置不相邻，则交换这两个位置，可以产生一个新的合法排列；将所有$h_i$变为$n+1-h_i$，也可以得到一个新的合法排列。设$dp[i][j]$表示长度为 i ，第 i 位高度为 j 且是山峰的方案数，有：
$$dp[i][j]=dp[i][j-1]+dp[i-1][i-j+1]$$
若 j 与 j - 1 的位置不相邻，则交换两个位置，得到长度为 i ，最后一位是 j - 1，且最后一位是山峰的排列，对应$dp[i][j-1]$；若相邻，则第 i - 1 位是 j - 1，且第 i - 1 位是山谷，把排列的所有$h_i$变为$n+1-h_i$，得到第 i - 1 位是 i - j + 1，且第 i - 1 位山峰的排列，对应$dp[i-1][i-j+1]$。
这个做法比较神仙，不容易想出来。另一种更容易想到的做法是设$dp[i]$表示 1 到 i 的数组成的第一个位置是山峰的合法排列数，然后有：
$$dp[i]=\sum_{j=1}^i[j\bmod 2=1]\binom{i-1}{j-1}dp[j-1]\cdot dp[i-j]$$
其中 j 表示枚举 i 在第 j 个位置，因为 i 一定是山峰所以 j 一定是奇数。$\dbinom{i-1}{j-1}dp[j-1]$表示枚举在剩下 i - 1 个数中的$j-1$个放在 i 左边并组成合法排列的方案数，$dp[i-j]$表示把剩下的数放在右边并组成合法排列的方案数。注意第 j + 1 个位置一定是山谷，但$dp[i-j]$中第一位是山峰，这样做正确的原因是第一位是山峰和第一位是山谷的方案数相等。
还有好多做法，不一一写了，参考资料：https://www.cnblogs.com/cj-chd/p/9967904.html 。
#include<cstdio>
int n, p, dp[4210][4210], ans;
int main() {
scanf("%d%d", &n, &p);
dp[1][1] = 1;
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++) dp[i][j] = (dp[i][j - 1] + dp[i - 1][i - j + 1]) % p;
for (int i = 1; i <= n; i++) ans = (ans + dp[n][i] * 2 % p) % p;
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P2391
常见套路，可以把操作倒过来做，用并查集维护，每次把染过色的都合并，操作时直接跳过染过色的，这样每个位置只会被染色一次，复杂度$O(n\log n)$。
#include<cstdio>
int n, m, p, q, c[1000100];
inline void swap(int &a, int &b) { int t = a; a = b; b = t; }
struct usetnode { int fa; };
struct uset {
usetnode nds[1000100];
int find(int x) {
if (nds[x].fa == x) return x;
return nds[x].fa = find(nds[x].fa);
}
inline void merge(int x, int y) {
x = find(x), y = find(y);
if (x < y) swap(x, y);
nds[y].fa = x;
}
inline void init() { for (int i = 1; i <= n + 1; i++) nds[i].fa = i; }
}uset;
int main() {
scanf("%d%d%d%d", &n, &m, &p, &q);
uset.init();
for (int i = m; i >= 1; i--) {
int l = (i * p + q) % n + 1, r = (i * q + p) % n + 1;
if (l > r) swap(l, r);
for (int j = uset.find(l); j <= r; j = uset.find(j)) c[j] = i, uset.merge(j, j + 1);
}
for (int i = 1; i <= n; i++) printf("%d\n", c[i]);
return 0;
}https://www.luogu.com.cn/problem/CF559C
棋盘比较大，而黑格子比较少，可以围绕黑格子进行 DP。将终点也看作黑格子，设$dp[i]$表示从起点到达第 i 个黑格子且不经过其他黑格子的方案数，那么根据减法公式有：
$$dp[i]=\binom{x_i+y_i-2}{x_i-1}-\sum_{valid(j)}dp[j]\cdot\binom{x_i-x_j+y_i-y_j}{x_i-x_j}$$
其中$valid(j)$表示第 j 个黑格子可以到达第 i 个黑格子。
#include<cstdio>
#include<algorithm>
const int MOD = 1e9 + 7;
int h, w, n, dp[2010], fac[200100], invfac[200100];
struct coordinate {
int x, y;
bool operator < (const coordinate &b) const {
if (x != b.x) return x < b.x;
return y < b.y;
}
}cdts[2010];
void exgcd(int a, int b, int &x, int &y) {
if (!b) { x = 1; y = 0; return; }
exgcd(b, a % b, y, x);
y -= a / b * x;
}
inline int inv(int a) { int x, y; exgcd(a, MOD, x, y); return (x % MOD + MOD) % MOD; }
inline int binom(int n, int m) { return (long long)fac[n] * invfac[m] % MOD * invfac[n - m] % MOD; }
int main() {
scanf("%d%d%d", &h, &w, &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &cdts[i].x, &cdts[i].y);
cdts[0].x = 1, cdts[0].y = 1; cdts[n + 1].x = h, cdts[n + 1].y = w;
n++;
std::sort(cdts + 1, cdts + n + 1);
fac[0] = 1;
for (int i = 1; i <= h + w; i++) fac[i] = (long long)fac[i - 1] * i % MOD;
invfac[h + w] = inv(fac[h + w]);
for (int i = h + w - 1; i >= 0; i--) invfac[i] = (long long)invfac[i + 1] * (i + 1) % MOD;
for (int i = 1; i <= n; i++) {
dp[i] = binom(cdts[i].x + cdts[i].y - 2, cdts[i].x - 1);
for (int j = 1; j < i; j++)
if (cdts[j].y <= cdts[i].y) dp[i] = (dp[i] - (long long)binom(cdts[i].x + cdts[i].y - cdts[j].x - cdts[j].y, cdts[i].x - cdts[j].x) * dp[j] % MOD + MOD) % MOD;
}
printf("%d\n", dp[n]);
return 0;
}https://www.luogu.com.cn/problem/P1600
常用技巧，桶+差分统计子树信息。将一条路径分为起点到顶端，以及顶端的子节点到终点两部分，然后对每个节点统计有多少玩家能被观察到，稍微推推式子，不难发现只要起点或终点在子树内，且满足以下条件之一：
$$w[x]+depth[x]=depth[s]$$
$$w[x]-depth[x]=dis-depth[t]$$
其中$s,t$分别表示起点和终点，$dis$表示 s 到 t 的路径长度。另外设$ca$表示$s,t$的$lca$。
可以设想在起点到顶端这条路径上加入$depth[s]$这个值，在顶端的子节点到终点这条路径上加入$dis-depth[t]$这个值，那么我们分别枚举所有节点，然后看看在这个节点上有几个$depth[s]$与$w[x]+depth[x]$相等，有几个$dis-depth[t]$与$w[x]-depth[x]$相等即可。像这种多次操作，最后统一询问的问题，显然可以直接树上差分解决。至于存储插入的值，可以用std::vector。
现在的问题是如何统计在当前节点上某种值有几个，不难想到用桶。然而每个节点都开一个桶显然不行，这就用到了桶+差分的技巧，即开一个桶记录当前所有已经访问过的节点所有的值的个数，然后子树内的个数等于遍历子树后的个数减去遍历前的个数。这个技巧之前也写过，就不多说了。这样整个问题就解决了，总复杂度$O(n)$。
如果实在不会桶+差分也可以直接线段树合并，也是很好理解的，不过复杂度是$O(n\log n)$的，而且常数很大，占的空间也多。好像还能树上启发式合并，不过我不会。
#include<cstdio>
#include<vector>
#include<utility>
int n, m, ans[300100], w[300100], f[300100][20], depth[300100], cnt1[600100], cnt2[600100];
struct edge { int to, next; };
struct graph {
int ecnt = 1, head[300100];
edge edges[600100];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
std::vector<std::pair<int, int> > w1[300100], w2[300100];
void dfs1(int x, int lst) {
depth[x] = depth[g.edges[lst ^ 1].to] + 1;
f[x][0] = g.edges[lst ^ 1].to;
for (int i = 1; i < 20; i++) f[x][i] = f[f[x][i - 1]][i - 1];
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
dfs1(g.edges[i].to, i);
}
}
inline void swap(int &a, int &b) { int t = a; a = b; b = t; }
inline int lca(int x, int y) {
if (depth[x] < depth[y]) swap(x, y);
for (int i = 19; i >= 0; i--)
if (depth[f[x][i]] >= depth[y]) x = f[x][i];
if (x == y) return x;
for (int i = 19; i >= 0; i--)
if (f[x][i] ^ f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
void dfs2(int x, int lst) {
int s1 = cnt1[w[x] + depth[x]], s2 = cnt2[w[x] - depth[x] + n];
for (std::vector<std::pair<int, int> >::iterator i = w1[x].begin(); i != w1[x].end(); i++) cnt1[i -> first] += i -> second;
for (std::vector<std::pair<int, int> >::iterator i = w2[x].begin(); i != w2[x].end(); i++) cnt2[i -> first] += i -> second;
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
dfs2(g.edges[i].to, i);
}
ans[x] += cnt1[w[x] + depth[x]] - s1 + cnt2[w[x] - depth[x] + n] - s2;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v); g.addedge(v, u);
}
dfs1(1, 0);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
for (int i = 1; i <= m; i++) {
int s, t; scanf("%d%d", &s, &t);
int ca = lca(s, t), dis = depth[s] + depth[t] - (depth[ca] << 1);
w1[s].push_back(std::make_pair(depth[s], 1));
w1[f[ca][0]].push_back(std::make_pair(depth[s], -1));
w2[t].push_back(std::make_pair(dis - depth[t] + n, 1));
w2[ca].push_back(std::make_pair(dis - depth[t] + n, -1));
}
dfs2(1, 0);
for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
return 0;
}https://www.luogu.com.cn/problem/P4163
十分套路的状压，设$dp[s][i]$表示由状态 s 里的所有数组成的排列中模 d 等于 i 个方案数，那么直接枚举在末尾接上哪个数，使用刷表法更新即可。虽然我不喜欢刷表法，但是这题填表法似乎不太好做。
然而给出的数字里有重复，需要去重，直接计一下每种数的个数，然后除以对应的阶乘即可。
常常用状压来代替枚举排列，这样可以把复杂度从阶乘降到 2 的幂，其本质在于状压通过状态划分把某些状态合并在了一起并统一计算，从而达到降到复杂度的效果。
#include<cstdio>
#include<cstring>
int t, n, d, dp[1100][1010], cnt[10], fac[11], ans;
char s[11];
int main() {
fac[0] = 1;
for (int i = 1; i <= 10; i++) fac[i] = fac[i - 1] * i;
scanf("%d", &t);
while (t--) {
memset(dp, 0, sizeof dp); memset(cnt, 0, sizeof cnt);
scanf("%s %d", s + 1, &d);
n = strlen(s + 1);
for (int i = 1; i <= n; i++) cnt[s[i] - '0']++;
dp[0][0] = 1;
for (int stt = 0; stt < (1 << n); stt++)
for (int i = 0; i < d; i++)
for (int j = 1; j <= n; j++)
if (!(stt & (1 << j - 1))) dp[stt | (1 << j - 1)][(i * 10 + s[j] - '0') % d] += dp[stt][i];
ans = dp[(1 << n) - 1][0];
for (int i = 0; i <= 9; i++) ans /= fac[cnt[i]];
printf("%d\n", ans);
}
return 0;
}https://www.luogu.com.cn/problem/P3226
一个有趣的构造思路：将一个数的三倍放在右边，二倍放在下边，那么相当于在二维矩阵中选择若干不相邻的数(正睿的题中也有类似思路，不过是一维情况)，可以直接状压求方案数。
枚举所有数，如果当前数没有被加入到矩阵过那么就以它为左上角构造矩阵。由唯一分解定理可以知道每个数只会被放在一个矩阵中。显然矩阵的长和宽都是$\log$级别的，因此状压的复杂度可以接受。
把dp[19][2050]写成了dp[2050][19]调了一个多小时。
#include<cstdio>
#include<cstring>
const int MOD = 1e9 + 1;
int n, dp[19][2050], a[19][11], len[19], rcnt, ans = 1;
bool vis[100100];
int main() {
scanf("%d", &n);
for (int x = 1; x <= n; x++) {
if (vis[x]) continue;
a[1][1] = x; vis[x] = true; rcnt = len[1] = 1;
for (int j = 2; a[1][j - 1] * 3 <= n; j++) a[1][j] = a[1][j - 1] * 3, len[1] = j, vis[a[1][j]] = true;
for (int i = 2; a[i - 1][1] * 2 <= n; i++) {
a[i][1] = a[i - 1][1] * 2; vis[a[i][1]] = true; len[i] = 1;
for (int j = 2; a[i][j - 1] * 3 <= n; j++) a[i][j] = a[i][j - 1] * 3, len[i] = j, vis[a[i][j]] = true;
rcnt = i;
}
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
for (int i = 1; i <= rcnt; i++) {
for (int s = 0; s < (1 << len[i]); s++) {
if (s & (s << 1)) continue;
for (int s1 = 0; s1 < (1 << len[i - 1]); s1++) {
if ((s1 & (s1 << 1)) || (s & s1)) continue;
dp[i][s] = (dp[i][s] + dp[i - 1][s1]) % MOD;
}
}
}
int ansx = 0;
for (int s = 0; s < (1 << len[rcnt]); s++) ansx = (ansx + dp[rcnt][s]) % MOD;
ans = (long long)ans * ansx % MOD;
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P4516
设$dp[x][j][0/1][0/1]$表示以节点 x 为根的子树内放了 j 个监控，且子树内除 x 外的节点都被覆盖，且 x 自身 没有 / 有 放监控，没有 / 有 被覆盖时的方案数。然后树形背包+分类讨论即可。
因为在转移时 k 可以等于 0，所以像以前写的那样滚动数组的话会导致错误的状态转移，再开个数组存一下上一个子节点更新完后的 dp 值即可。
#include<cstdio>
const int MOD = 1e9 + 7;
int n, m, dp[100100][110][2][2], dpb[100100][110][2][2], size[100100];
struct edge { int to, next; };
struct graph {
int ecnt = 1, head[100100];
edge edges[200100];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
void dfs(int x, int lst) {
size[x] = dp[x][0][0][0] = dp[x][1][1][0] = 1;
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = g.edges[i].to;
dfs(v, i);
for (int j = min(size[x] + size[v], m); j >= 0; j--) {
dpb[x][j][0][0] = dp[x][j][0][0], dp[x][j][0][0] = 0;
dpb[x][j][0][1] = dp[x][j][0][1], dp[x][j][0][1] = 0;
dpb[x][j][1][0] = dp[x][j][1][0], dp[x][j][1][0] = 0;
dpb[x][j][1][1] = dp[x][j][1][1], dp[x][j][1][1] = 0;
}
for (int j = min(size[x] + size[v], m); j >= 0; j--) {
for (int k = max(j - size[x], 0); k <= j && k <= size[v]; k++) {
dp[x][j][0][0] = (dp[x][j][0][0] + (long long)dpb[x][j - k][0][0] * dp[v][k][0][1] % MOD) % MOD;
dp[x][j][0][1] = (dp[x][j][0][1] + (long long)dpb[x][j - k][0][1] * (dp[v][k][0][1] + dp[v][k][1][1]) % MOD + (long long)dpb[x][j - k][0][0] * dp[v][k][1][1] % MOD) % MOD;
dp[x][j][1][0] = (dp[x][j][1][0] + (long long)dpb[x][j - k][1][0] * (dp[v][k][0][0] + dp[v][k][0][1]) % MOD) % MOD;
dp[x][j][1][1] = (dp[x][j][1][1] + (long long)dpb[x][j - k][1][1] * (((long long)dp[v][k][0][0] + dp[v][k][0][1] + dp[v][k][1][0] + dp[v][k][1][1]) % MOD) % MOD + (long long)dpb[x][j - k][1][0] * (dp[v][k][1][0] + dp[v][k][1][1]) % MOD) % MOD;
}
}
size[x] += size[v];
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v); g.addedge(v, u);
}
dfs(1, 0);
printf("%d\n", (dp[1][m][0][1] + dp[1][m][1][1]) % MOD);
return 0;
}https://www.luogu.com.cn/problem/P3084
设$dp[i]$表示第 i 个位置一定有一个点时，前 i 个位置最多有几个点。
一个技巧是把每个区间的点数一定是 1 这个条件拆为每个区间的点数小于等于 1 且大于等于 1。由区间点数小于等于 1 ，可以得出对于所有包含 i 的区间$[l,r]$，$dp[i]$能转移来的范围都小于 l 。由区间点数大于等于 1，可以得出对于所有右端点在 i 左侧的区间$[l,r]$，$dp[i]$能转移来的范围都大于等于 l 。由此可以确定$dp[i]$能转移来的范围。
具体来说可以在每个位置存一下所有右端点恰好在这个位置的所有区间。设所有包含 i 的区间的最小 l 为$minl[i]$，所有在 i 左侧的最大 l 为$maxl[i]$，那么$minl[i]$可以先继承$minl[i+1]$的值，然后再在以 i 为右端点的区间的 l 中取最小值，复杂度$O(n+m)$。这样写正确的原因是$minl[i+1]$对应的区间可能包含 i ，这时拿来更新$minl[i]$显然是对的；否则不包含 i ，这时并不影响 i 的答案更新，因为这时以 i 为右端点的区间的左端点一定小于$minl[i+1]$。不过当不存在以 i 为右端点的区间时，这时得出的$minl[i]$显然是错的，所以在继承$minl[i+1]$时还要和 i 取最小值。
$maxl[i]$的求解也是同理，不过不用考虑边界情况。
不难发现$[maxl[i],minl[i])$是单调递增的，于是可以用单调队列优化一下，总复杂度$O(n+m)$。
不过有的位置是不可能有点的，所以当第 i 个位置不可能有点时，令$dp[i]=-1$，然后 DP 时判断一下就可以了。至于最后的答案可以再增加一个第 n + 1 个位置，然后答案显然就是$dp[n+1]-1$。
#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
int n, m, dp[200100], minl[200100], maxl[200100], ans = -1;
std::vector<int> sec[200100];
std::deque<std::pair<int, int> > q;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int l, r; scanf("%d%d", &l, &r);
sec[r].push_back(l);
}
minl[n + 1] = n + 1;
for (int i = n; i >= 1; i--) {
minl[i] = min(minl[i + 1], i);
for (std::vector<int>::iterator j = sec[i].begin(); j != sec[i].end(); j++) minl[i] = min(minl[i], *j);
}
for (int i = 1; i <= n + 1; i++) {
maxl[i] = maxl[i - 1];
for (std::vector<int>::iterator j = sec[i - 1].begin(); j != sec[i - 1].end(); j++) maxl[i] = max(maxl[i], *j);
}
int cur = 0;
for (int i = 1; i <= n + 1; i++) {
while (cur < minl[i]) {
if (dp[cur] == -1) { cur++; continue; }
while (!q.empty() && q.back().second <= dp[cur]) q.pop_back();
q.push_back(std::make_pair(cur, dp[cur]));
cur++;
}
while (!q.empty() && q.front().first < maxl[i]) q.pop_front();
if (!q.empty()) dp[i] = q.front().second + 1;
else dp[i] = -1;
}
if (dp[n + 1] != -1) printf("%d\n", dp[n + 1] - 1);
else printf("-1\n");
return 0;
}https://www.luogu.com.cn/problem/CF451E
容斥经典题，有 n 种颜色，每种颜色有$a_i$个球，求取出 s 个球的方案数。考虑弱化版，若$\forall i\in[1,n],s\le a_i$，也就是说任何位置无论怎么选都可行，那么方案数就是$\dbinom{s+n-1}{n-1}$。
当$\exist i\in[1,n],s>a_i$时，可以容斥计算。设$b_i$表示第 i 种颜色取出了几个球，$S$表示所有$b_i>a_i$即不合法的颜色集合，$f(S)$表示$S$对应的方案数，$g(S)$表示钦定状态为$S$时的方案数，那么有：
$$g(S)=\sum_{T\supseteq S}f(S)$$
反演一下可以得到：
$$f(S)=\sum_{T\supseteq S}(-1)^{|T|-|S|}g(T)$$
而$g(S)$可以快速计算：
$$g(S)=\binom{s-\sum_{i\in S}(a_i+1)+n-1}{n-1}$$
因为第 i 种颜色一定不合法，至少选了$a_i+1$个，那么就把总球数减去$a_i+1$，表示先把这些球选上，那么这个颜色剩余的球就随便选了，转化为了没有任何限制的方案数即上面的弱化版。枚举所有状态，然后计算即可。
这个组合数看起来有点大不好算，实际上由于$n-1$很小，所以可以把$\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}$拆为$\dfrac{1}{m!}\cdot \dfrac{n!}{(n-m)!}$，不算计算逆元的复杂度的话两者都可以$O(m)$计算，所以没问题。
#include<cstdio>
const int MOD = 1e9 + 7;
int n, ans;
long long m, a[21];
inline long long min(long long a, long long b) { return a < b ? a : b; }
void exgcd(int a, int b, int &x, int &y) {
if (!b) { x = 1; y = 0; return; }
exgcd(b, a % b, y, x);
y -= a / b * x;
}
inline int inv(int a) { int x, y; exgcd(a, MOD, x, y); return (x % MOD + MOD) % MOD; }
int binom(long long n, long long m) {
if (n < m) return 0;
if (n < MOD && m < MOD) {
m = min(m, n - m);
int a = 1, b = 1;
for (int i = 1; i <= m; i++) a = (long long)a * i % MOD, b = (long long)b * (n - i + 1) % MOD;
return (long long)inv(a) * b % MOD;
}
return (long long)binom(n / MOD, m / MOD) * binom(n % MOD, m % MOD) % MOD;
}
inline int pwr_1(int k) { return (k & 1) ? -1 : 1; }
int main() {
scanf("%d%lld", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int s = 0; s < (1 << n); s++) {
long long k = n + m - 1;
int pc = 0;
for (int i = 1; i <= n; i++)
if (s & (1 << i - 1)) k -= a[i] + 1, pc++;
ans = ((ans + pwr_1(pc) * binom(k, n - 1)) % MOD + MOD) % MOD;
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/CF932E
关于第二类斯特林数，有一个常用的性质：
$$x^n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}\binom{x}{i}i!=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline i}$$
根据这个性质，将幂拆开，推一下式子。
$$\sum_{i=1}^n\binom{n}{i}i^k\\=\sum_{i=1}^n\binom{n}{i}\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\binom{i}{j}j!\\=\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=1}^n\binom{n}{i}\binom{i}{j}\\=\sum_{j=1}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=1}^n\binom{n}{j}\binom{n-j}{i-j}\\=\sum_{j=1}^k\begin{Bmatrix}k\\j\end{Bmatrix}\binom{n}{j}j!\sum_{i=0}^{n-j}\binom{n-j}{i}\\=\sum_{j=1}^k\begin{Bmatrix}k\\j\end{Bmatrix}\binom{n}{j}j!\cdot 2^{n-j}$$
然后$O(k^2)$预处理一下第二类斯特林数即可。
#include<cstdio>
const int MOD = 1e9 + 7;
int n, k, s[5010][5010], ans;
inline int min(int a, int b) { return a < b ? a : b; }
void exgcd(int a, int b, int &x, int &y) {
if (!b) { x = 1; y = 0; return; }
exgcd(b, a % b, y, x);
y -= a / b * x;
}
inline int inv(int a) { int x, y; exgcd(a, MOD, x, y); return (x % MOD + MOD) % MOD; }
inline int binom(int n, int m) {
if (n < m) return 0;
m = min(m, n - m);
int a = 1, b = 1;
for (int i = 1; i <= m; i++) a = (long long)a * i % MOD, b = (long long)b * (n - i + 1) % MOD;
return (long long)inv(a) * b % MOD;
}
inline int pwr(int x, int k) {
if (k < 0) return 0;
int ans = 1;
for (; k; x = (long long)x * x % MOD, k >>= 1)
if (k & 1) ans = (long long)ans * x % MOD;
return ans;
}
int main() {
scanf("%d%d", &n, &k);
s[0][0] = 1;
for (int i = 1; i <= k; i++)
for (int j = 1; j <= i; j++) s[i][j] = (s[i - 1][j - 1] + (long long)j * s[i - 1][j] % MOD) % MOD;
for (int i = 1, fac = 1; i <= k; i++, fac = (long long)fac * i % MOD)
ans = (ans + (long long)s[k][i] * binom(n, i) % MOD * fac % MOD * pwr(2, n - i) % MOD) % MOD;
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P6185
首先可以令$a_i=a_i-b_i$，那么问题变为将 a 序列全部变为 0 。不难看出对于第二种操作，无论怎么操作和都不会变，那么对于每个第二种操作将两个位置连无向边，这样只要连通块内的和是 0 就可以了，于是可以把一个连通块看作一个点，接下来只需要考虑第一种操作。
对于第一种操作，也在两个端点所属的连通块之间连一条无向边。然后若得到的图是二分图，那么只有两侧节点权值之和相等时才可行。若不是二分图，那么所有节点权值之和是偶数时才可行。对于每个连通分量，判断是否是二分图并统计权值和即可。
#include<cstdio>
#include<cstring>
int t, n, m, a[100100], col[100100];
long long lw, rw, w[100100];
bool vis[100100];
struct usetnode { int fa; long long w; };
struct uset {
usetnode nds[100100];
int find(int x) {
if (nds[x].fa == x) return x;
return nds[x].fa = find(nds[x].fa);
}
inline void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
nds[y].fa = x;
nds[x].w += nds[y].w;
}
inline void init() { for (int i = 1; i <= n; i++) nds[i].fa = i, nds[i].w = a[i]; }
inline long long getw(int x) { return nds[find(x)].w; }
}uset;
struct edge { int to, next; };
struct graph {
int ecnt, head[100100];
edge edges[200100];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
inline void clear() { memset(head, 0, sizeof(int) * (n + 1)); memset(edges, 0, sizeof(edge) * (ecnt + 1)); ecnt = 1; }
}g;
struct operation { int opt, u, v; }opts[100100];
bool dfs(int x, int c, int lst) {
col[x] = c;
if (c == 1) lw += w[x];
else rw += w[x];
bool ok = true;
for (int i = g.head[x]; i; i = g.edges[i].next) {
if ((i ^ lst) == 1) continue;
int &v = g.edges[i].to;
if (col[v] == c) ok = false;
if (!col[v] && !dfs(v, -c, i)) ok = false;
}
return ok;
}
int main() {
scanf("%d", &t);
while (t--) {
memset(col, 0, sizeof(int) * (n + 1)); memset(vis, 0, sizeof(bool) * (n + 1)); memset(w, 0, sizeof(long long) * (n + 1));
g.clear();
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
int b; scanf("%d", &b);
a[i] -= b;
}
uset.init();
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &opts[i].opt, &opts[i].u, &opts[i].v);
if (opts[i].opt == 2) uset.merge(opts[i].u, opts[i].v);
}
for (int i = 1; i <= m; i++)
if (opts[i].opt == 1)
g.addedge(uset.find(opts[i].u), uset.find(opts[i].v)), g.addedge(uset.find(opts[i].v), uset.find(opts[i].u));
for (int i = 1; i <= n; i++) w[uset.find(i)] = uset.getw(i);
bool ans = true;
for (int i = 1; i <= n; i++)
if (!col[uset.find(i)]) {
lw = rw = 0;
if (dfs(uset.find(i), 1, 0) && lw != rw) ans = false;
else if ((lw + rw) & 1) ans = false;
}
if (ans) printf("YES\n");
else printf("NO\n");
}
return 0;
}https://www.luogu.com.cn/problem/P1360
一个常见的套路：把区间和拆为前缀和之差。然后不难想到一个所有数都相等的数列的差分数组除第一个位置外全部是 0 ，那么若两个前缀和的差是一个均衡时期，这两个前缀和的差分数组除第一位外一定相等。对于每天的前缀和算一下差分，然后哈希统计答案即可。
#include<cstdio>
#include<cstdlib>
#include<ctime>
int n, m, sum[100100][31], dif[100100][31], ans;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
template<int mod> struct hashtable {
const int MOD = mod;
int head[mod], next[100100], val[100100], cnt, w[31];
inline void init() {
srand((unsigned long long)mod * time(NULL));
for (int i = 1; i < m; i++) w[i] = rand();
}
inline int h(int *dif) {
int ans = 0;
for (int i = 1; i < m; i++) ans = (ans + (long long)w[i] * ((dif[i] + MOD) % MOD) % MOD) % MOD;
return ans;
}
inline void insert(int x, int v) {
val[++cnt] = v;
next[cnt] = head[x];
head[x] = cnt;
}
inline int find(int x) {
int ans = 0x3fffffff;
for (int i = head[x]; i; i = next[i]) ans = min(ans, val[i]);
return ans;
}
};
hashtable<19260817> h1; hashtable<1000007> h2;
int main() {
scanf("%d%d", &n, &m);
h1.init(); h2.init();
h1.insert(0, 0); h2.insert(0, 0);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
for (int j = 0; j < m; j++) {
if (x & (1 << j)) sum[i][j] = sum[i - 1][j] + 1;
else sum[i][j] = sum[i - 1][j];
if (j) dif[i][j] = sum[i][j] - sum[i][j - 1];
}
int hv1 = h1.h(&dif[i][0]), hv2 = h2.h(&dif[i][0]);
int lst1 = h1.find(hv1), lst2 = h2.find(hv2);
if (lst1 == lst2) ans = max(ans, i - lst1);
h1.insert(hv1, i); h2.insert(hv2, i);
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P2061
有两种思路，都挺妙的。一种是把所有操作按照$h_i$从小到大排序，那么依次进行区间赋值即可，可以离散化后用线段树维护。
另一种是先离散化，然后对每个坐标维护覆盖它的所有区间。考虑依次遍历每个坐标，然后一个区间$[l,r)$可以把它拆为在坐标 l 加入这个区间，在坐标 r 删除这个区间，使用std::multiset维护即可。
#include<cstdio>
#include<set>
#include<algorithm>
int n, cnt, vl[80100];
long long ans;
struct operation {
int type, x, h;
operation(int tv = 0, int xv = 0, int hv = 0): type(tv), x(xv), h(hv) {}
bool operator < (const operation &b) const { return x < b.x; }
}opts[80100];
std::multiset<int> s;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int l, r, h; scanf("%d%d%d", &l, &r, &h);
opts[++cnt] = operation(1, l, h); vl[cnt] = l;
opts[++cnt] = operation(2, r, h); vl[cnt] = r;
}
std::sort(vl + 1, vl + cnt + 1);
int vn = std::unique(vl + 1, vl + cnt + 1) - vl - 1;
for (int i = 1; i <= cnt; i++) opts[i].x = std::lower_bound(vl + 1, vl + vn + 1, opts[i].x) - vl;
std::sort(opts + 1, opts + cnt + 1);
int cur = 1;
for (int i = 1; i <= vn; i++) {
for (; cur <= cnt && opts[cur].x <= i; cur++) {
if (opts[cur].type == 1) s.insert(opts[cur].h);
else if (opts[cur].type == 2) s.erase(s.find(opts[cur].h));
}
if (i != vn && !s.empty()) ans += (long long)*(--s.end()) * (vl[i + 1] - vl[i]);
}
printf("%lld\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P2017
看到没有环，不难联想到拓扑排序。可以对每条有向边记录入度，然后执行拓扑排序，对于每条没标记过的无向边标记一下方向即可，若没有遍历全部节点则没有可行方案。
#include<cstdio>
#include<queue>
#include<algorithm>
int n, m1, m2, deg[100100], cnt, ecnt;
struct edge { int to, next, w; bool tag; };
struct graph {
int ecnt = 1, head[100100];
edge edges[400100];
inline void addedge(int u, int v, int w) {
edges[++ecnt].to = v;
edges[ecnt].w = w;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
inline int type(int i) { return edges[i].to && edges[i ^ 1].to ? 2 : 1; }
inline int havetag(int i) { return edges[i].tag || edges[i ^ 1].tag; }
}g;
std::queue<int> q;
struct undiredge {
int u, v, w;
undiredge(int uv = 0, int vv = 0, int wv = 0): u(uv), v(vv), w(wv) {}
bool operator < (const undiredge &b) const { return w < b.w; }
}edges[100100];
inline void topo() {
for (int i = 1; i <= n; i++) if (!deg[i]) q.push(i);
while (!q.empty()) {
int x = q.front();
q.pop();
cnt++;
for (int i = g.head[x]; i; i = g.edges[i].next) {
int &v = g.edges[i].to;
if (g.type(i) == 2 && !g.havetag(i)) g.edges[i].tag = true;
else {
deg[v]--;
if (!deg[v]) q.push(v);
}
}
}
}
int main() {
scanf("%d%d%d", &n, &m1, &m2);
for (int i = 1; i <= m1; i++) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v, 0); g.addedge(0, 0, 0);
deg[v]++;
}
for (int i = 1; i <= m2; i++) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v, i); g.addedge(v, u, i);
}
topo();
if (cnt == n) {
for (int x = 1; x <= n; x++) for (int i = g.head[x]; i; i = g.edges[i].next)
if (g.edges[i].tag) edges[++ecnt] = undiredge(x, g.edges[i].to, g.edges[i].w);
std::sort(edges + 1, edges + ecnt + 1);
for (int i = 1; i <= ecnt; i++) printf("%d %d\n", edges[i].u, edges[i].v);
}
else printf("-1\n");
return 0;
}https://www.luogu.com.cn/problem/P1607
考虑一个经典问题，选择尽量多的区间使得每个位置最多被一个区间覆盖。有两种做法，一种是线性 DP，另一种是贪心，先把所有区间按照右端点从小到大排序，然后能选就选。这样做正确的原因是假设当前区间能选但不选，这样下一个选择的区间相当于充当了当前这个区间的贡献，但右端点比当前区间大，显然不优。
本题也可以这样做，用线段树维护区间最值即可。
#include<cstdio>
#include<algorithm>
int k, n, c, sumw, ans;
struct section {
int l, r, w;
section(int lv = 0, int rv = 0, int wv = 0): l(lv), r(rv), w(wv) {}
bool operator < (const section &b) const {
if (r != b.r) return r < b.r;
return l > b.l;
}
}sec[50010];
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
struct segtreenode { int maxw, addtag; };
struct segtree {
segtreenode nds[80100];
inline int ls(int x) { return x << 1; }
inline int rs(int x) { return x << 1 | 1; }
inline void pushup(int x) { nds[x].maxw = max(nds[ls(x)].maxw, nds[rs(x)].maxw); }
inline void pushdown(int x) {
if (!nds[x].addtag) return;
nds[ls(x)].maxw += nds[x].addtag; nds[ls(x)].addtag += nds[x].addtag;
nds[rs(x)].maxw += nds[x].addtag; nds[rs(x)].addtag += nds[x].addtag;
nds[x].addtag = 0;
}
inline void add(int x, int l, int r, int ql, int qr, int v) {
if (ql > qr) return;
if (ql <= l && r <= qr) {
nds[x].maxw += v;
nds[x].addtag += v;
return;
}
pushdown(x);
int mid = l + (r - l >> 1);
if (ql <= mid) add(ls(x), l, mid, ql, qr, v);
if (mid + 1 <= qr) add(rs(x), mid + 1, r, ql, qr, v);
pushup(x);
}
inline int query(int x, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return nds[x].maxw;
pushdown(x);
int mid = l + (r - l >> 1), ans = 0;
if (ql <= mid) ans = max(ans, query(ls(x), l, mid, ql, qr));
if (mid + 1 <= qr) ans = max(ans, query(rs(x), mid + 1, r, ql, qr));
return ans;
}
}seg;
int main() {
scanf("%d%d%d", &k, &n, &c);
for (int i = 1; i <= k; i++) scanf("%d%d%d", &sec[i].l, &sec[i].r, &sec[i].w);
std::sort(sec + 1, sec + k + 1);
for (int i = 1; i <= k; i++) {
int v = seg.query(1, 1, n, sec[i].l, sec[i].r);
if (v < c) {
int d = min(c - v, sec[i].w);
seg.add(1, 1, n, sec[i].l, sec[i].r - 1, d);
ans += d;
}
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P6187
一共会有$\gcd(n,k)$个独立的环，每个环的大小为$\dfrac{n}{\gcd(n,k)}$。由排序不等式可以得出，将大的数放在尽量相邻的位置是更优的。所以对于每个环，依次把当前最大的数放入即可。
首先将序列排序，然后显然每$\dfrac{n}{\gcd(n,k)}$个数会放入一个环中，通过想象可以得出，除开头结尾外都是每隔一个位置放在一起，直接计算即可。
因为答案只与$\dfrac{n}{\gcd(n,k)}$有关，所以可以记忆化一下，这样只会对 n 的每个约数计算一次，复杂度$O(n\sqrt n)$。
#include<cstdio>
#include<algorithm>
int n, m, a[200100];
long long ans[200100];
int gcd(int a, int b) {
if (!b) return a;
return gcd(b, a % b);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), ans[0] += (long long)a[i] * a[i];
std::sort(a + 1, a + n + 1);
while (m--) {
int k; scanf("%d", &k);
int t = gcd(n, k), s = n / t;
if (!k) t = 0;
if (!ans[t]) {
for (int i = 1; i <= n; i += s) {
for (int j = i; j < i + s - 2; j++) ans[t] += (long long)a[j] * a[j + 2];
ans[t] += (long long)a[i] * a[i + 1] + (long long)a[i + s - 2] * a[i + s - 1];
}
}
printf("%lld\n", ans[t]);
}
return 0;
}https://www.luogu.com.cn/problem/AT1974
以$x=B$和$x=B+1$两条直线为分界线，将过程划分为三个阶段。首先可以从$(1,1)$走到$(x,y)\ (1\le x\le H-A,y=B)$，然后再从$(x,y)$走到$(x,y+1)$，然后再从$(x,y)\ (1\le x\le H-A,y=B+1)$走到$(H,W)$。将方案数相乘即可，即：
$$\sum_{x=1}^{H-A}\binom{x+B-2}{x-1}\binom{H-x+W-B-1}{H-x}$$
限制在第二个阶段从$(x,y)$走到$(x,y+1)$的原因是若直接算从起点走到$(x,y)\ (1\le x\le H-A,y=B+1)$的方案数，这个坐标可能由它上面的坐标即$(x-1,y)$走过来，这样的话再去算从它走到$(H,W)$的方案数也会算上它向下走的方案，这样就会重复。
#include<cstdio>
const int MOD = 1e9 + 7;
int r, c, a, b, fac[200100], invfac[200100], ans;
void exgcd(int a, int b, int &x, int &y) {
if (!b) { x = 1; y = 0; return; }
exgcd(b, a % b, y, x);
y -= a / b * x;
}
inline int inv(int a) { int x, y; exgcd(a, MOD, x, y); return (x % MOD + MOD) % MOD; }
inline int binom(int n, int m) {
if (n < m) return 0;
return (long long)fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
}
int main() {
scanf("%d%d%d%d", &r, &c, &a, &b);
fac[0] = 1;
for (int i = 1; i <= r + c; ++i) fac[i] = (long long)fac[i - 1] * i % MOD;
invfac[r + c] = inv(fac[r + c]);
for (int i = r + c - 1; i >= 0; --i) invfac[i] = (long long)invfac[i + 1] * (i + 1) % MOD;
for (int x = 1; x <= r - a; ++x) ans = (ans + (long long)binom(x + b - 2, x - 1) * binom(r - x + c - b - 1, r - x) % MOD) % MOD;
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/AT1975
对于这种存在至少一个某种特殊对象的计数，可以用减法公式转化为总方案数减去不存在这种特殊对象的方案数，因为是存在至少一个，这样的话直接枚举哪里存在并计算有时候容易重复计数，然后可能就得容斥，而不存在只可能存在 0 个，这个条件有时候很好处理。
那么对于本题，总方案数就是$10^N$。不存在俳句的方案数可以状压计算。
考虑将一个数 x 划分为 n 个数的和$x=\sum_{i=1}^n a_i$，可以想象成有 x 个位置和 n 种颜色，依次考虑所有颜色，对于第 i 种颜色，从第一个还没染色的位置开始向后染色$a_i$个位置。若对于任意三个数$i+j+k=x$，存在前缀的长度等于 i，紧接着中间一段的长度等于 j，剩下的后缀长度等于 k，那么第$i$和第$i+1$个位置、第$i+j$和第$i+j+1$个位置、第$n$和第$n+1$个位置的颜色一定不相同。
转化为二进制，将下一个位置的颜色与自身不相同的位置设为 1，那么一个俳句对应的 01 串的第$X$位、第$X+Y$位和第$X+Y+Z$位为 1，而其他位为 0。将一个数列转为 01 串，依次考虑每个$a_i$，先在末尾加上$a_i-1$个 0，再加上 1 个 1，若俳句对应的 01 串是数列对应的 01 串的子集，则存在至少一个俳句。可以状压 DP，设$dp[i][s]$表示长度为 i 的数列转为 01 串后最后$X+Y+Z$位是 s 时不存在俳句的方案数，直接转移即可。
#include<cstdio>
const int MOD = 1e9 + 7;
int n, x, y, z, dp[41][140100], ans = 1;
int main() {
scanf("%d%d%d%d", &n, &x, &y, &z);
int lim = 1 << x + y + z, haiku = (1 << x + y + z - 1) | (1 << y + z - 1) | (1 << z - 1);
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int ls = 0; ls < lim; ++ls) {
if ((ls & haiku) == haiku) continue;
for (int j = 1; j <= 10; ++j) {
int ns = ((ls << j) | (1 << j - 1)) & (lim - 1);
if ((ns & haiku) == haiku) continue;
dp[i][ns] = (dp[i][ns] + dp[i - 1][ls]) % MOD;
}
}
}
for (int i = 1; i <= n; ++i) ans = (long long)ans * 10 % MOD;
for (int s = 0; s < lim; ++s) ans = (ans - dp[n][s] + MOD) % MOD;
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/CF3B
考虑只有一种重量时，显然优先拿价值大的更优。扩展到本题的情况，核心思想是两个重量为 1 的物品可以合并为一个重量为 2 的物品。那么将没被拿出的物品中价值最大的两个 1 的价值的和以及价值最大的一个 2 的价值比较，取更优的那个决策。当剩余容量为 1 时需要特判取一个 1 还是放弃一个 1 并取最优的 2。
还可以直接枚举两种重量的物品分别选了多少个，排序后预处理前缀和然后$O(1)$计算价值和即可。
#include<cstdio>
#include<algorithm>
#include<utility>
#include<functional>
int n, m, v1cnt, v2cnt, ans;
std::pair<int, int> v1[100100], v2[100100];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
int t, v; scanf("%d%d", &t, &v);
if (t == 1) v1[++v1cnt] = std::make_pair(v, i);
else v2[++v2cnt] = std::make_pair(v, i);
}
std::sort(v1 + 1, v1 + v1cnt + 1, std::greater<std::pair<int, int> >());
std::sort(v2 + 1, v2 + v2cnt + 1, std::greater<std::pair<int, int> >());
int cur1 = 1, cur2 = 1;
for (; m; ) {
if (cur1 <= v1cnt && cur2 <= v2cnt) {
if (m == 1) {
if (cur1 == 1 || v1[cur1].first >= v2[cur2].first - v1[cur1 - 1].first) ans += v1[cur1++].first;
else ans += v2[cur2++].first - v1[--cur1].first;
--m;
}
else {
if (v1[cur1].first + v1[cur1 + 1].first >= v2[cur2].first) ans += v1[cur1].first + v1[cur1 + 1].first, cur1 += 2;
else ans += v2[cur2++].first;
m -= 2;
}
}
else if (cur1 <= v1cnt) ans += v1[cur1++].first, --m;
else if (cur2 <= v2cnt) {
if (m > 1) ans += v2[cur2++].first, m -= 2;
else {
if (cur1 > 1 && v2[cur2].first >= v1[cur1 - 1].first) ans += v2[cur2++].first - v1[--cur1].first, --m;
else break;
}
}
else break;
}
printf("%d\n", ans);
for (int i = 1; i < cur1 && i <= v1cnt; ++i) printf("%d ", v1[i].second);
for (int i = 1; i < cur2 && i <= v2cnt; ++i) printf("%d ", v2[i].second);
return 0;
}https://www.luogu.com.cn/problem/CF3D
合法括号序列的性质是转化为 1 和 -1 的序列后任意一个位置的前缀和大于等于 0 ，且最后一位的前缀和等于 0。对于一个位置，对它产生影响的只有它前面的那些位置。可以先钦定所有问号都是右括号，然后从前到后依次遍历序列并维护前缀和，对于一个问号如果它的前缀和小于 0 ，那就把这个位置对应的前缀中代价最小的一个问号从右括号改成左括号。可以直接用堆维护，复杂度$O(n\log n)$。
#include<cstdio>
#include<cstring>
#include<queue>
#include<functional>
#include<utility>
int n, k, a[50010], b[50010];
long long ans;
char s[50100];
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > q;
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; ++i) if (s[i] == '?') scanf("%d%d", &a[i], &b[i]);
int sum = 0;
for (int i = 1; i <= n; ++i) {
if (s[i] == '(') ++sum;
else if (s[i] == ')') --sum;
else if (s[i] == '?') {
ans += b[i];
s[i] = ')';
q.push(std::make_pair(a[i] - b[i], i));
--sum;
}
while (!q.empty() && sum < 0) {
ans += q.top().first;
s[q.top().second] = '(';
q.pop();
sum += 2;
}
}
sum = 0;
bool ok = true;
for (int i = 1; i <= n; ++i) {
if (s[i] == '(') ++sum;
else if (s[i] == ')') --sum;
if (sum < 0) ok = false;
}
if (sum != 0) ok = false;
if (ok) printf("%lld\n%s\n", ans, s + 1);
else printf("-1\n");
return 0;
}https://www.luogu.com.cn/problem/CF4D
经典问题，可以把能够嵌套的矩形之间连有向边，然后求 DAG 上的最长路径即可，复杂度$O(n^2)$。
另一种更好的做法是先把二元组按照第一维排序，然后求最长上升子序列即可，复杂度$O(n\log n)$。
#include<cstdio>
#include<cstring>
int n, w[5010], h[5010], dp[5010], ddp[5010], ans, ansx;
bool vis[5010];
void dfs(int x) {
vis[x] = true;
if (x == n + 1) return;
for (int i = 1; i <= n + 1; ++i)
if (w[i] < w[x] && h[i] < h[x]) {
if (!vis[i]) dfs(i);
if (dp[x] < dp[i] + 1) dp[x] = dp[i] + 1, ddp[x] = i;
}
}
void print(int x) {
if (x == n + 1 || !x) return;
print(ddp[x]);
printf("%d ", x);
}
int main() {
scanf("%d", &n); scanf("%d%d", &w[n + 1], &h[n + 1]);
for (int i = 1; i <= n; ++i) scanf("%d%d", &w[i], &h[i]);
memset(dp, -0x3f, sizeof(int) * (n + 2));
dp[n + 1] = 0;
for (int i = 1; i <= n; ++i) if (dp[i] < 0) dfs(i);
for (int i = 1; i <= n; ++i)
if (ans < dp[i]) ans = dp[i], ansx = i;
printf("%d\n", ans);
print(ansx);
return 0;
}