对多步容斥不熟练啊，我建议我自己看看这个。

link。

首先将问题弱化为 1-d，我们待定容斥系数 $f_i$，可以写出答案的式子：$\sum\limits_{i=a}^nf_i\binom{n}{i}2^{n-i}$。解释就是，我们想让 $\binom{n}{i}2^{n-i}$ 达到“至少”的效果，但是明显会算重，所以通过这个容斥系数 $f_i$ 达到“恰好”的效果，于是原题“至少”的答案就是这个。

每一个“恰好” $i$ 个的方案数在最终的答案中的贡献次数为 $1$，也就是说 $\sum\limits_{j=a}^if_j\binom{i}{j}=1$。这个的意思就是如果至少有 $i$ 的方案数重了，那么它一定是从前面开始重的（就是说 $1,\dots,i-1$ 的随便摆的部分跟它重了），所以从前面开始容斥。

然后就好算了，可以直接得出 $f_i=\sum\limits_{j=a}^{i-1}f_j\binom{i-1}{j-1}$，或者你也可以用下吸收公式推式子。

但实际上这个题还有一些常数的优化，具体可以看看 Siyuan 的博客。

#include<bits/stdc++.h>
#define il __inline__ __attribute__((always_inline))
constexpr int kMod=998244353;
__int128 sum;
int n,m,A,B,i,j,k;
int coef[2][3100],pw[9000100],bin[3100][3100];
il void MCase() {
  for(k=0; k<2; ++k) {
    coef[k][0]=1;
    for(int i=(k?B:A); i<=(k?m:n); ++i) coef[k][i]=1ll*(((i-(k?B:A))&1)?-1:1)*bin[i-1][(k?B:A)-1]%kMod*bin[k?m:n][i]%kMod;
  }
  int res=0;
  for(i=A; i<=n; ++i)
    for(j=B; j<=m; ++j) (res+=1ll*coef[0][i]*coef[1][j]%kMod*pw[(n-i)*(m-j)]%kMod)%=kMod;
  std::printf("%d\n",res<0?res+kMod:res);
}
signed main(int argc,char const* argv[]) {
  pw[0]=1;
  for(i=1; i<9000100; ++i) pw[i]=1ll*pw[i-1]*2%kMod;
  bin[0][0]=1;
  for(i=1; i<3100; ++i) {
    bin[i][0]=1;
    for(j=1; j<=i; ++j) bin[i][j]=(bin[i-1][j]+bin[i-1][j-1])%kMod;
  }
  for(; ~std::scanf("%d%d%d%d",&n,&m,&A,&B);) MCase();
  return 0;
}

link。

首先将问题弱化为 1-d，我们待定容斥系数 $f_i$，可以写出答案的式子：$\sum\limits_{i=a}^nf_i\binom{n}{i}2^{n-i}$。解释就是，我们想让 $\binom{n}{i}2^{n-i}$ 达到“至少”的效果，但是明显会算重，所以通过这个容斥系数 $f_i$ 达到“恰好”的效果，于是原题“至少”的答案就是这个。

每一个“恰好” $i$ 个的方案数在最终的答案中的贡献次数为 $1$，也就是说 $\sum\limits_{j=a}^if_j\binom{i}{j}=1$。这个的意思就是如果至少有 $i$ 的方案数重了，那么它一定是从前面开始重的（就是说 $1,\dots,i-1$ 的随便摆的部分跟它重了），所以从前面开始容斥。

然后就好算了，可以直接得出 $f_i=\sum\limits_{j=a}^{i-1}f_j\binom{i-1}{j-1}$，或者你也可以用下吸收公式推式子。

但实际上这个题还有一些常数的优化，具体可以看看 Siyuan 的博客。

#include<bits/stdc++.h>
#define il __inline__ __attribute__((always_inline))
constexpr int kMod=998244353;
__int128 sum;
int n,m,A,B,i,j,k;
int coef[2][3100],pw[9000100],bin[3100][3100];
il void MCase() {
  for(k=0; k<2; ++k) {
    coef[k][0]=1;
    for(int i=(k?B:A); i<=(k?m:n); ++i) coef[k][i]=1ll*(((i-(k?B:A))&1)?-1:1)*bin[i-1][(k?B:A)-1]%kMod*bin[k?m:n][i]%kMod;
  }
  int res=0;
  for(i=A; i<=n; ++i)
    for(j=B; j<=m; ++j) (res+=1ll*coef[0][i]*coef[1][j]%kMod*pw[(n-i)*(m-j)]%kMod)%=kMod;
  std::printf("%d\n",res<0?res+kMod:res);
}
signed main(int argc,char const* argv[]) {
  pw[0]=1;
  for(i=1; i<9000100; ++i) pw[i]=1ll*pw[i-1]*2%kMod;
  bin[0][0]=1;
  for(i=1; i<3100; ++i) {
    bin[i][0]=1;
    for(j=1; j<=i; ++j) bin[i][j]=(bin[i-1][j]+bin[i-1][j-1])%kMod;
  }
  for(; ~std::scanf("%d%d%d%d",&n,&m,&A,&B);) MCase();
  return 0;
}

发现终于最讨厌的还是和自己的相同的人的样子。

A

傻逼题，不算复杂度差不多得了，显然交换 $S$ / $T$ 的选出区间中的任意位置不影响答案，于是前缀和即可。

B

清新题，只不过我的确不会...部分分设置不太合理。

你考虑用 $O(h ^ 2 w ^ 2)$ 的时间钦定两个点 $(x_1, y_1), (x_2, y_2)$ 研究线段，同时令 $a = |x_1 - x_2|, b = |y_1 - y_2|$。如果你做过 仪仗队 那么很容易想到中间一共有 $\gcd(a, b)$ 个点，把这些点当作盒子，把它们拍到序列上，则我们有 $\gcd(a, b) - 1$ 个盒子，$n - 2$ 个点（钦定端点必选）。如果我们令 $k=\lfloor\frac{d}{{\rm dis}((0, 0), (\frac{a}{\gcd(a, b)}, \frac{b}{\gcd(a, b)}))}\rfloor$，则每个球放进的盒子编号需差 $\geqslant k$。

赋予组合意义，则每个球存在「体积」的概念，且该「体积」为 $k - 1$，考虑将其压缩， 那么答案式子就出来了 $\binom{\gcd(a, b) - 1 - (k - 1) - (n - 2)(k - 1)}{n - 2}$，那个 $k - 1$ 是右端点已经必选了，所以少了 $k - 1$ 个盒子。

考虑优化，注意答案取决于 $a$ 和 $b$，可以乘个系数来优化。

C

清新题，部分分非常暗示。

有个显然的 observation 是一个结点一定从子树中至多选两个未被选择的结点转移，那么就可以直接可并堆启发式合并什么的来转移。

主要问题是为什么不是儿子中选呢？你考虑一个结点 $x$，其父亲 $pre(x)$ 只有 $x$ 一个儿子，而 $x$ 有三个儿子，并且 $x$ 把其中两个儿子选完了，那么 $pre(x)$ 一定是从 $x$ 的另一个儿子转移上来，所以必须把子树考虑完。

D

你出你🐎的 BM 呢😅😅。

题意大概是这样，「每次操作选出区间中的一个 LIS（strictly），满足其开端是极靠近左端点且大于 $A$ 的位置，答案即这个 LIS 的末尾，做一个轮换后弹出序列末端」。

首先做几个观察。

Observation 1：每次被弹出的都是区间最大值。

证明：显然，你考虑有一个最大的值在钦定的 LIS 的前或后，都会被先行选择 / 扩展进来。

Observation 2（key observation）：如果对一个区间插入若干个值，插入顺序不影响最终序列的长相。

证明：每次插入进去的值不可能成为序列的最大值，所以弹出的数固定。并且插入进的数是根据严格偏序关系插进去的，所以顺序不影响长相。

仅凭以上两个观察，此题的奇怪操作怎么看也不像是个 ${\rm polylog}$，选择对序列做 Sqrt Decomposition，接下来我们探讨整块间的处理方式和散块的做法，因为操作的特殊性我们并不需要做 8 种情况的伞兵讨论。

• 整块间：你考虑每个整块上维护一个大根堆，然后整块的后继继承该整块的最大值，该整块去除其最大值即可；
• 散块：把所有需要插入的元素存一个懒标在右边散块放出来，因为 Observation 2，我们贪心优先把值较小的懒标放出去即可。

#include <bits/stdc++.h>
template <class T> inline void chmax(T& a, const T b) { a = a > b ? a : b; }
template <class T> inline void chmin(T& a, const T b) { a = a < b ? a : b; }
inline long long rd() {
  long long x = 0; bool f = 0; char ch = getchar();
  while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + (ch & 15), ch = getchar();
  return f ? -x : x;
}
/** @brief
 * 选出一个 LIS，满足开始是极靠近 l 的大于 A 的位置，答案即序列的末端，然后用 A 替换序列开头，做一个轮换，弹出序列末端
 * Observation 1：每次被弹出的都是区间最大值
 * Trick：序列分块
 * Section 1：整块
   * 整块上维护一个堆，整块间下一块继承上一块的最大值
 * Section 2：散块
   * 维护一个小根堆，每次散块暴力重构
 * key observation：插入顺序不影响序列的长相
*/
constexpr int BS = 650;
int n, m, a[400100], pos[400100];
int L[660], R[660];
std::priority_queue<int> max[660];
std::priority_queue<int, std::vector<int>, std::greater<int>> tag[660];
void push(int i, int x) { max[i].emplace(x); }
void setBound(int i) { L[i] = (i - 1) * BS + 1, R[i] = i * BS; }
int Qry(int i, int l, int r, int x) {
  if (tag[i].size()) {
    for (int j = L[i]; j <= R[i]; ++j)
      if (int t = a[j]; tag[i].top() < t)
        a[j] = tag[i].top(), tag[i].pop(), tag[i].emplace(t);
  }
  while (max[i].size()) max[i].pop();
  while (tag[i].size()) tag[i].pop();
  for (int j = l; j <= r; ++j)
    if (a[j] > x) std::swap(a[j], x);
  for (int f = L[i]; f <= R[i]; ++f) push(pos[L[i]], a[f]);
  return x;
}
int Mdf(int i, int x) {
  if (x >= max[i].top()) return x;
  int res = max[i].top(); max[i].pop();
  max[i].emplace(x), tag[i].emplace(x);
  return res;
}
signed main() {
  n = rd(), m = rd();
  for (int i = 1; i <= n; ++i)
    push(pos[i] = (i - 1) / BS + 1, a[i] = rd());
  for (int i = 1; i <= pos[n]; ++i) setBound(i);
  R[pos[n]] = n;
  for (int l, r, a; m--;) {
    l = rd(), r = rd(), a = rd();
    if (pos[l] == pos[r] && l <= r) printf("%d\n", Qry(pos[l], l, r, a));
    else {
      a = Qry(pos[l], l, R[pos[l]], a);
      for (int u = pos[l] + 1 > pos[n] ? 1 : pos[l] + 1; u != pos[r]; u = u + 1 > pos[n] ? 1 : u + 1)
        a = Mdf(u, a);
      printf("%d\n", Qry(pos[r], L[pos[r]], r, a));
    }
  }
  return 0;
}

不太了解这个东西的具体定义是什么，总之应该是一个用数据结构维护 DP 状态的某几个维度的 trick 吧。

事实上你可以把这篇 post 理解为三个题的解集。

先直接来看 noi2020 - Destiny 这个题。

给定一棵树 $T = (V, E)$ 和点对集合 $\mathcal Q \subseteq V \times V$ ，满足对于所有 $(u, v) \in \mathcal Q$，都有 $u \neq v$，并且 $u$ 是 $v$ 在树 $T$ 上的祖先。其中 $V$ 和 $E$ 分别代表树 $T$ 的结点集和边集。求有多少个不同的函数 $f$ : $E \to \{0, 1\}$（将每条边 $e \in E$ 的 $f(e)$ 值置为 $0$ 或 $1$），满足对于任何 $(u, v) \in \mathcal Q$，都存在 $u$ 到 $v$ 路径上的一条边 $e$ 使得 $f(e) = 1$。由于答案可能非常大，你只需要输出结果对 $998,244,353$（一个素数）取模的结果。

我们略过 DP 的过程，直接给出其定义 $f(x,j)$ 表示考虑子树 $i$，限制条件的 $v\in{\rm subtree}(x)$ 且限制 $(u,v)$ 尚未被满足，$u$ 的深度最深且 $j={\rm dep}(u)$ 的不同映射 $f:E_{{\rm subtree}(x)}\rightarrow\{0,1\}$ 数量，以及其转移$f(x,i)= f(x,i)\sum\limits_{y\in{\rm suf}(x)}\left(\sum\limits_{j=0}^{{\rm dep}(x)}f(y,j)+\sum\limits_{j=0}^{i}f(y,j)\right)+f(y,i)\sum\limits_{j=0}^{i-1}f(x,j)$。

令 $g(x)$ 为 $f(i)$ 的前缀和，得到平方级算法。

如果我们考虑把 DP 的第二维度状态放到线段树上，那么子树的合并就可以放到线段树上去做，即使用线段树的合并 trick 来做 DP。

我们来看看合并的具体过程。贴近实现，我们令 ${\rm merge}:\{(x,y,l,r,s_x,s_y)\}\rightarrow{\rm node}$ 表示线段树合并的过程，其中 $s_x$ & $s_y$ 表示 DP 的前缀和（即 $g$），在实现（以及下文的讲解）中，均把这两个变量视作别名。

有这样几种情形需要探讨。

• $l=r$：此时应该把 $f(y,l)$ 合并到 $f(x,l)$ 中，直接对线段树结点维护的 DP 值进行修改；
• $x=\Omega$：此时 $f(x)$ 的 DP 值并没有意义，在本题中可以视作零。于是打乘法标记即可；
• $y=\Omega$：与上一条类似。

于是得到解决，参考实现。

再来看 pkuwc2018 - Minimax 这个题。

给出一棵有 $n$ 的结点的二叉有根树，并给出其叶子结点的权值，对于一个非叶子结点，其权值有 $p_i$ 概率取得儿子中的最大值， $1-p_i$ 的概率取得最小值。

令 $\{v_{i}\}$ 表示最终根结点（$1$-th 结点）的所有可能取值（升序排列），其个数记为 $m$，每一个 $v_i$ 取得的概率记为 $r_i$，将其按照 ${\rm hash}(i)=i\times v_i\times r_i$ 的规则求出 $\sum_i{\rm hash}(i)$。

与上一题类（完 全）似（一 致）地，同样略过 DP 的过程，给出其定义 $f(i,j)$ 表示结点 $i$ 取得值 $j$ 的概率，以及其转移 $f(i,j)=\sum\limits_{v\in{\rm suf}(i)} f(v,j)\left(p_i\sum\limits_{1\leqslant k<j}f(v',k)+(1-p_i)\sum\limits_{j<k}f(v',k)\right)$，其中 $v'$ 表示 ${\rm suf}(i)\setminus\{v\}$ 中的唯一取值。

令 $g(i)$ 为 $f(i)$ 的前缀和（显然这里的 $\infty$ 并不是「真正的无限」），得到平方级的算法。

同样考虑把 DP 的第二维度状态放到线段树上，在线段树合并时维护 $s_x$ & $s_y$ 表示 DP 的前缀和，直接维护即可。

参考实现。

最后来看到 codeforces - 671D / Roads in Yusland。

给定一棵 $n$ 个点的以 $1$ 为根的树。有 $m$ 条路径 $(x,y)$，保证 $y$ 是 $x$ 或 $x$ 的祖先，每条路径有一个权值。你要在这些路径中选择若干条路径，使它们能覆盖每条边，同时权值和最小。

这题的平方 DP 都有一定难度……看了 duyi 的题解挺久才理解……不过如果做过 noi2020 - Destiny 的话应该会好很多。

称 ${\rm route}(u,v)$ 中的 $u$ 为起点，$v$ 为终点，在 $v$ 决策一个 route 是否被选择。参考 noi2020 - Destiny 的状态设计，令 $f(x,i)$ 表示在 ${\rm subtree}(x)$ 中选择了若干 routes，其中终点深度最深并且高于 ${\rm dep}(x)$ 的深度为 $i$ 的最优方案。

转移即 $f(x,i)=\min\limits_{y\in{\rm suf}(x)}\{f(y,i)+\sum\limits_{z\in{\rm suf}(x)\setminus\{y\}}g(z)\}$，其中 $g(x)=\min\limits_{1\leqslant i<{\rm dep}(x)}\{f(x,i)\}$，还需要考虑每条 route 带来的额外转移，转移式显然不赘。这些 transforming formulae 也许带有一些构造成分在里面，至少我觉得不太自然……

然后考虑线段树合并优化，你需要支持区间增量 & 全局查询最小值 & 合并（与此同时区间取 $\min$）& 单点取 $\min$。因为 $O((n+m)\log_2n)$ 的空间复杂度并不能通过此题。

考虑以时间换空间，我们采用权值平衡树 & 启发式合并来解决（参考实现中给出的是 std::set）。

平衡树上每个结点维护一个 2-tuple $(i,f(x,i))$，以第一关键字排序。我们依次考虑如何支持上文的操作。

• 区间增量：如果及时把 $i>{\rm dep}(x)$ 的元素弹出，这就变成了全局增量，直接维护即可；
• 全局查询最小值：这个是本题最妙的地方，因为关键字的选取，平衡树无法简单地取出最小值，我们需要更多的性质。注意到 $\forall j<k,s.t.f(x,j)<f(x,k)$，此时的 $k$ 都是无用的，可以直接删除，这得出了此题的单调性。如此全局最小值就是平衡树上最右边的结点；
• 合并：启发式合并即可；
• 单点取 $\min$：相当于插入操作，直接来即可，需要注意一些不是特别细的细节（雾）。

如此时间复杂度退成了 $O((n+m)\log_2^2n)$，但是空间复杂度优化到了 $O(n+m)$，可以通过此题。

参考实现。