容斥
当具有复杂限定条件的原问题难以直接求解时，应主动考虑容斥。原问题一般有若干个坏事件，并对不发生任何坏事件的情况计数。通常的处理方法是钦定发生若干个坏事件，计算方案数，并赋予一定的系数反演得到原答案。
设 $f(\mathbb{S})$ 为不发生 $\mathbb{S}$ 中任意事件的方案数，$g(\mathbb{T})$ 表示钦定发生 $\mathbb{T}$ 中所有事件的方案数，则有
$$f(\mathbb{S})=\sum_{\mathbb{T}\subseteq\mathbb{S}}(-1)^{\lvert\mathbb{T}\rvert}g(\mathbb{T})$$直接套用原式可以解决如 CF451E Devu and Flowers 的问题。
一类 DP 方法
一个经典问题，从网格 $(0,0)$ 处每次向右或向下，不经过任何障碍，最终到达 $(n,n)$ 的方案数。
可以直接递推，$f_{i,j}$ 表示从 $(0,0)$ 不经过障碍到 $(i,j)$ 的方案数，障碍点不进行转移。这样可以 $O(n^2)$ 解决。
当 $n$ 很大时可以考虑对不经过障碍的限制容斥。该问题的 $g(\mathbb{T})$ 形如一系列组合数的乘积，每个组合数代表两个障碍之间的路径数。重复项很多，考虑 DP 处理。
$f_i$ 表示最后一个坏事件发生在障碍 $i$ 的 $g(\mathbb{T})$ 之和。则有
$$f_i=\binom{x_i+y_i}{x_i}-\sum_{j}^{i-1}\binom{x_i+y_i-x_j-y_j}{x_i-x_j}f_j$$记障碍总数为 $m$，原问题答案就是
$$\sum_{i=1}^m{\binom{2n-x_i-y_i}{n-x_i}f_i}$$接下来考虑这个问题的加强版。
对于一个排列 $P$，定义 $F(P)$ 如下： 对于一个 $(N+2)\times (N+2)$ 的网格图，行列标号为 $0\sim N+1$，从 $(0,0)$ 走到 $(N+1,N+1)$ 在不经过 $(i,P_i)$ 情况下的方案数。给定一个残缺的排列，对于其所有补全求函数之和。
可以类似的设 $f_{i,j,k}$ 表示设定第 $i$ 个障碍在 $(i,j)$ 且最后一个坏事件在 $(i,j)$，目前已经确定了 $k$ 个未知的位置，所有 $g(\mathbb{T})$ 的和。则转移是类似的，可以得到复杂度为 $O(n^5)$ 的做法。
注意到组合数成为转移瓶颈，考虑拆开组合数，直接递推路径数。重新设计状态，$f_{i,j,k,0/1,0/1}$ 表示最后位于 $(i,j)$，确定了 $k$ 个未知点，当前行是否钦定了障碍，当前列是否钦定了障碍的 $g(\mathbb{T})$ 之和。
转移则有两种：
-
当前位置不作为被钦定的障碍，则转移的意义为维护路径数。
-
当前位置作为被钦定的障碍，则由于 $\lvert\mathbb{T}\rvert$ 增加 $1$，转移系数为 $-1$。
可以说，针对被钦定集合 $\mathbb{T}$ 的大小变化决定转移系数，是这一类 DP 的核心。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int maxn = 200 + 10;
constexpr int mod = 998244353;
int a[maxn];
i64 f[maxn][maxn][maxn][2][2];
i64 fac[maxn];
i64 C[maxn][maxn];
bool vis[maxn];
int main()
{
fac[0] = C[0][0] = 1;
for (int i=1;i<maxn;++i)
{
fac[i] = fac[i - 1] * i % mod;
C[i][0] = C[i][i] = 1;
for (int j=1;j<i;++j)
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
}
ios::sync_with_stdio(0);
cin.tie(0);
int n, m = 0;
cin >> n;
for (int i=2;i<=n+1;++i)
{
cin >> a[i];
if (!++a[i]) ++m;
else vis[a[i]] = 1;
}
f[1][1][0][1][1] = 1;
a[n+2] = -1;
for (int i=1;i<=n+2;++i)
for (int j=1;j<=n+2;++j)
for (int k=0;k<=m;++k)
{
if (i == 1 && j == 1) continue;
if (k && !a[i] && !vis[j]) f[i][j][k][1][1] = (mod - (f[i-1][j][k-1][0][0] + f[i-1][j][k-1][1][0] + f[i][j-1][k-1][0][0] + f[i][j-1][k-1][0][1]) % mod) % mod;
if (a[i] == j) f[i][j][k][1][1] = (mod - (f[i-1][j][k][0][0] + f[i-1][j][k][1][0] + f[i][j-1][k][0][0] + f[i][j-1][k][0][1]) % mod) % mod;
f[i][j][k][0][0] = (f[i-1][j][k][0][0] + f[i][j-1][k][0][0] + f[i-1][j][k][1][0] + f[i][j-1][k][0][1]) % mod;
f[i][j][k][0][1] = (f[i-1][j][k][0][1] + f[i-1][j][k][1][1]) % mod;
f[i][j][k][1][0] = (f[i][j-1][k][1][0] + f[i][j-1][k][1][1]) % mod;
}
i64 ans = 0;
for (int i=0;i<=m;++i)
ans = (ans + f[n+2][n+2][i][0][0] * fac[m-i] % mod + mod) % mod;
cout << ans << endl;
return 0;
}
给定一个大小为 $n$ 的树，保证 $n$ 为偶数且小于 $5000$。 您需要给树上的点两两配对，对于一组对子 $(u,v)$, 在树上将 $u\to v$ 的路径染色，定义一个配对方案合法当且仅当所有边都有颜色。 求方案数对 $10^9+7$ 取模。
朴素的 DP 是设 $f_{u,i}$ 表示考虑到 $u$ 为根的子树，有 $i$ 个点尚未匹配的合法方案数。复杂度是 $O(n^3)$，无法通过。
可以对边是否满足被覆盖进行容斥，考虑 $g(\mathbb{T})$ 的求法。
未被染色的边相当于将图割成了几个连通块，每个块的方案是块内点两两匹配的方案数。$n$ 个点两两匹配的方案数为 $\prod_{i=1}^{\frac{n}{2}}2i-1$。
这样就只和树上连通块大小相关，可以进行 DP 了。
$f_{u,i}$ 表示处理到了 $u$ 所在的子树，且 $u$ 所在的连通块大小为 $i$ 的 $g(\mathbb{T})$ 之和。转移时枚举是否断边即可。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int maxn = 5000 + 10;
constexpr int mod = 1000000000 + 7;
vector<int> G[maxn];
i64 fac[maxn], inv[maxn];
i64 C(int n, int m)
{
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
i64 qp(i64 a, i64 b)
{
i64 c = 1;
for (; b; b>>=1, a=a*a%mod)
if (b & 1) c=c*a%mod;
return c;
}
i64 f[maxn][maxn], t[maxn], g[maxn];
int s[maxn];
void dfs(int u, int fa)
{
f[u][1] = 1;
s[u] = 1;
for (int v : G[u])
{
if (v == fa) continue;
dfs(v, u);
memcpy(t, f[u], sizeof(t));
memset(f[u], 0, sizeof(f[u]));
for (int i=1;i<=s[u];++i)
for (int j=0;j<=s[v];++j)
f[u][i + j] = (f[u][i + j] + t[i] * f[v][j]) % mod;
s[u] += s[v];
for (int i=1;i<=s[u];++i)
f[u][0] = (f[u][0] - f[u][i] * g[i] % mod + mod) % mod;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
g[0] = 1;
for (int i=2;i<maxn;i+=2)
g[i] = g[i - 2] * (i - 1) % mod;
fac[0] = 1;
for (int i=1;i<maxn;++i) fac[i] = fac[i - 1] * i % mod;
inv[maxn - 1] = qp(fac[maxn - 1], mod - 2);
for (int i=maxn-2;i>=0;--i) inv[i] = inv[i + 1] * (i + 1) % mod;
int n;
cin >> n;
for (int i=1;i<n;++i)
{
int u, v;
cin >> u >> v;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
dfs(1, 0);
cout << mod - f[1][0] << endl;
return 0;
}
又一类 DP 方法
这一类问题一般有两类条件，其中一种条件较好用数值表达，另一种条件只能用容斥才方便刻画。一般可以按照数值顺序递推，容斥时只需要考虑新增加的项可能造成的重复。
T414900 开关灯
很容易想到记 $f_{i,j}$ 表示进行过不相同操作 $i$ 次，剩下 $j$ 个异色未翻转的方案数。
若不考虑不相同，可以直接组合意义枚举情况简单做。
转移的核心在于处理不相同。注意到若有两次相同操作，则相当于序列未变化，所以我们假设第 $i$ 次操作和之前某次相同，这个部分有 $i-1$ 的系数，操作是任意的，但前 $i-1$ 次操作不重，所以有系数 $\binom{n}{3}-(i-2)$。可知重复部分为 $(i-1)(\binom{n}{3}-(i-2))f_{i-2,j}$，减去即可。
P3214 [HNOI2011] 卡农
经典题。记长度为 $x$ 的合法序列方案数为 $f_x$。我们发现偶数约束是简单的，任意选择前 $x-1$ 个，根据奇偶性推出第 $x$ 个即可。下面还是只需要考虑第 $x$ 项，显然有 $f_{x-1}$ 种可能使第 $x$ 项为空集不合法。若 $x$ 与之前某项重复，则去除两项的序列合法，所以数量为 $(2^n-x+2)(x-1)f_{x-2}$。简单减去即可。
同时，这也是将限制放在过程中增量确定思想的一个体现。
