计数问题选讲

容斥篇

08:09 sconnect。求 $n(n\leq 15)$ 个点有向图中强连通子边图个数。

考虑图 $G$ 强连通当且仅当其不存在真子点集 $V'$ 满足 $∁_VV'$ 的边都是 $V$ 到 $V'$ 的。

尝试考虑 $\Theta(3^n)$ 的做法，状压 DP 枚举子集。设 $f_S$ 表示只考虑点集 $S$ 时强连通方案数量。

图经 tarjan 算法缩点后将成为 DAG。考虑拓扑排序逐步剥离 DAG 的无出度点，故对无出度点容斥。

枚举无出度点集 $T$，它们缩点后互相孤立。则 $∁_ST$ 往 $T$ 边随意连。则 $f_S=2^{e(S,S)}-\sum_{T⫋S}f_{∁_ST}g_T2^{e(∁_ST,T)}$。考虑容斥系数 $g$。

根据 $1,2,3\dots$ 个无出度点情况类推得 $g_S=\sum_{k=1}^{|S|}\prod_{\cup_{i=1}^ks_i=S,\sum_{i=1}^k|s_i|=|S|,s_i\neq\emptyset,\min s_i<\min s_{i+1}}\prod_{i=1}^kf_{s_i}$（其中 $s_{1\dots k}$ 划分了 $S$）。

08:29 Endless Spin。$n(n\leq 50)$ 个元素，每次随机选择区间 $[l,r]$ 标记其中所有元素。求标记所有元素期望次数。

Min-Max 容斥：$\max_{s∈S}s=\sum_{T⊆S}(-1)^{|T|-1}\min_{t∈T}t$。

对于期望亦然成立。$E(\max_{s∈S}s)=\sum_{T⊆S}(-1)^{|T|-1}E(\min_{t∈T}t)$。

08:34 一层递归。初始为 $0$ 值每次随机或 $a_{1\dots n}$ 中的一个元素，求让 $x=\operatorname{or}_{i=1}^na_i$ 的期望。

设 $p_i$ 表示第 $i$ 位变成 $1$ 的期望，则根据 min-max 容斥考虑 $\min_{t∈T}p_t$，显然期望为 $\dfrac{n}{\sum_{i=1}^n[a_i\operatorname{or}t\neq 0]}$，可以 FWT 快速求解。

08:41 递归结束。

因为 $n$ 很大，不能用如上方法求 $\min$，故考虑观察性质。钦定某些球 $x_{1\dots k}$ 不能选，那么一共有 $\sum_{i=1}^{k+1}\operatorname{C}_{x_i-x_{i-1}}^2$ 可用区间数（$x_0=0,x_{k+1}=n+1$）。设 $f_{i,j,k}$ 为 上一个取了 $i$、球数奇偶性为 $j$，可用区间数为 $k$ 的方案数。

转移为 $f_{i,j,k}=\sum_{t=0}^{i-1}f_{t,j\oplus 1,k+\operatorname{C}_{i-t-1}^2}$。只要时间复杂度不超过 $\Theta(n^4)$ 即可。需要钦定 $0$ 一定不选。

DP 套 DP 篇

把内层 DP 值作为状态进行二层递推。可以理解为基于 DP 的 DFA。内层 DP 值域需要有限。

08:56 Hero meet devil。给定字符串 $S(|S|\leq 15,|\Sigma|=4)$，对于每个 $0\leq i\leq|S|$，问有多少长为 $m(m\leq 10^3)$ 的 $T$ 使得 $|\operatorname{lcs}(S,T)|=i$。

下层 DP 中求 $S$ 和 $T$ 的 LCS。则 $f_{i,j}=\max(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}+[S_i=T_j])$。把 DP 状态建图。把一列 $n$ 个元素压成一个点。

为减少状态数，考虑限制 $f_i∈\{f_{i-1},f_{i-1}+1\}$，则点数仅有 $\Theta(2^n)$，时间复杂度 $\Theta(2^nm|\Sigma|)$。

09:11 Square。给定 $n\times n(n\leq 8)$ 的 01 二维数组，某些位置必须为 $1$。对于每个 $0\leq i\leq n$，求多少种数组满足其中最大全 $0$ 正方形边长为 $i$。

下层 DP 中求最大正方形边长，转移为 $f_{i,j}=[a_{i,j}=0](\min(f_{i-1,j},f_{i,j-1},f_{i-1,j-1})+1)$。逐行 DP 转移过多，考虑转为轮廓线 DP。状态同时要记录轮廓线的 $m+1$ 个 DP 值、当前列数和历史最大值。

因为若 $f_{i,j}>0$，则 $f_{i,j}\geq f_{i,j}-1$，故状态数较少。

对于 $i$ 接近 $n$ 的情况，可以枚举 $i\times i$ 全 $0$ 正方形存在位置并将存在性与最大性容斥。于是将 $i$ 分为大小两部分，分别采用不同方式求解。

??:?? OneBlack。给定 $n\times m(n,m\leq 30)$ 的 012 二维数组，其中有些点确定为 $2$，其余点需要为 $0$ 或 $1$。问有多少种数组满足对于所有无 $2$ 的从 $(1,1)$ 走到 $(n,m)$ 的 $n+m-1$ 长路径（以下称路径）都恰好包含一个 $1$。

路径不会到的点可以随意选择。对于可能到的点，因为合法方案中到某个点所有路径含 $1$ 数一定相等，因此内层 DP $f_{i,j}$ 表示 $(1,1)$ 走到 $(i,j)$ 的所有路径中 $1$ 的个数。

因为 $f$ 值只有 $0$ 和 $1$ 且 $f$ 值为 $1$ 点后续一定都为 $1$，因此状态数很少，可以通过。

??:?? Jigsaw Puzzle。对于一个 $n\times m(n\leq 500,m\leq 6)$ 的棋盘的子集，求它有多少个子集可以被 $1\times 2$ 砖刚好覆盖。

原始内层逐行 DP 状态为 $2^8$ 个布尔值、上层 DP 需 $2^{64}$，考虑优化。因 贪心从左连续两空位填横砖 一定不会更劣（仅考虑轮廓线以下格子，若不纵造成下方点无法匹配，不横右方点也无法匹配），可将连续两空位方案重定向，状态数降到 $2^{21}$。

看起来状态数还是太大了。但如果先搜索转移能得到那些状态，会发现基于以上贪心算法得到的状态数远远少与 $2^{21}$，便可以通过了。

??:?? StringPath。给定长 $n+m-1$ 的字符串 $S$、$T$。求多少种 $n\times m(n,m\leq 8,|\Sigma|=26)$ 的矩阵满足存在两条从 $(1,1)$ 到 $(n,m)$ 长 $n+m-1$ 的路径沿途分别为 $S$ 和 $T$。

对于内层 DP，$f_{i,j,s,t}$ 表示到点 $(i,j)$ 时路径是否能为 $S$ 或 $T$ 的前缀。每个 $(i,j)$ DP 值有 $4$ 种，还是用轮廓线 DP 优化，状态数可降到 $4^m$。

枚举分类优化篇

??:?? The only survival。$n(n\leq 12)$ 个点无向完全图，边权为自然数且上限 $l(l\leq 10^9)$，求多少个图 $1$ 到 $n$ 最短路为 $k(k\leq 12)$。

考虑枚举 $1$ 到 $i$ 最短路 $d_i$。由此，对于边 $(u,v)$ 应当有 $w(u,v)\geq|d_u-d_v|$；同时，对于 $u>1$，需要有 $v$ 满足 $d_v+w(u,v)=d_u$。显然 $d_i$ 值可简化为 $0\dots k$ 和 $>k$。因点 $2\dots n-1$ 平等，枚举 $d_2$ 到 $d_{n-1}$ 中各标号数量并根据以上两个原则计算边方案数即可。

??:?? 扑克牌。$n(n\leq 30)$ 个元素 $(a_i,b_i)(a_i<10,b_i<3)$，需要找到排列 $p_{1\dots n}$ 的个数，满足对于 $1<i\leq n$，有 $a_{p_{i-1}}=a_{p_i}∨b_{p_{i-1}}=b_{p_i}$。每种 $(a,b)$ 个数最多为 $3$。

同 $a$ 元素连 $A$ 边、同 $b$ 连 $B$ 边。$A$ 边的团分为若干部分，每部分内部随便走，可缩为一些首、末 $b$ 值形式的边。对所有同 $a$ 元素搜索枚举即可。

缩完后 $b$ 值间共有 $3^2$ 种有向边。将 DP 状态设为 这 $9$ 种边的数量 进行递推，并记录 $A$ 团内部连接方案种数；最后，对于每种形态，需要乘上欧拉路的走法。

??:?? Substring Pairs。求所有长 $n(n\leq 200,|\Sigma|\leq 10^3)$ 字符串的本质不同 $m(m\leq 50)$ 长子串数的和。

设长串 $S$、子串 $T$。对于特定的 $T$，可以枚举其在 $S$ 中位置并经典容斥计算对应的 $S$ 数量。基于以上求解 只和的所有 $T$ 的 border 长有关，可依 border 集合分类，求各类的 $T$ 数量与答案。

尽管 $T$ 类型数似乎是 $\Theta(2^{|T|})$ 的，但因为 border 间的干涉非常严重，真正的 border 集合数量非常少，可通过加 border 后立即补全的 DFS 求出全部。

求每种 border 集合 $s$ 的 $T$ 个数，可以先转化为 border 集合包含 $s$，然后再暴力找包含 $s$ 的合法集合减掉容斥。

期望线性篇

将期望值拆为满足期望可加性的若干类型小期望，最后求和即可。

??:?? MST。给定 $n(n\leq 10)$ 的简单有效图，每条边在 $[0,1]$ 均匀随机。求图最小生成树长度和的期望。

根据概率原理，有边长相同的概率为 $\frac{1}{\infin}=0$，可忽略这种情况并认为最小生成树一定唯一。考虑一条边对总和的期望贡献。

边 $(u,v,w)$ 出现在最小生成树中，则 $u$ 和 $v$ 不能被长度小于 $w$ 的边连起来。枚举 $u$ 在小于 $w$ 边的联通分量 即可得到 $w$ 与 $(u,v)$ 不互通 的概率的关系，用传统状压 DP 即可。因为 DP 的系数永远是 $w^d$ 或 $(1-w)^d$，此关系是一个多项式 $p(w)=\sum_{i=0}^ka_iw^i$。则 $(u,v)$ 对最短路产生的期望贡献为 $∫_{w=0}^1p(w)=\sum_{i=0}^k\frac{a_i}{i+1}$。

??:?? ClosestRabbit。$n\times m(n,m\leq 20)$ 的矩阵随机放 $r$ 个球。随后将每个球与离它最近的球联通，对于同距离情况第二关键字为行号、第三关键字为列号。求连通块期望个数。

设 $u$ 最近点为 $f(u)$。转化为有向边 $(u,f(u))$，可形成基环树。原联通块数就是基环树的环数。

设点 $u$ 在环上前驱为 $p$，后继为 $s$，则 $\operatorname{dis}(u,p)\geq\operatorname{dis}(u,s)$，否则 $f(u)\neq s$，矛盾。此不等式绕环一圈即可得 环上相邻两点距离处处相等。

对于环上位置 $(x_u,y_u)$ 在比较中最小的点 $u$，因为上述结论，有 $f(p)=f(s)=u$。这个条件可以推出 环的长度只能为 $2$。

随后原问题变成了 求满足 $f(u)=v,f(v)=u$ 值的期望数对 $(u,v)$ 数。于是我们枚举位置对 $(x_1,y_1)$、$(x_2,y_2)$，求它们成为以上数对的概率。排除掉会破坏二元环性质的点的情况，然后乘上两个点都有球的概率即可。

??:?? BitToggler。给定长 $n(n\leq 20)$ 01 串 $S$、$i$（初值给定）与 $w=0$，重复操作直到 $S$ 全为 $0$：$i'\larr\operatorname{rand}(n)$，$w\larr w+|i-i'|$，$S_{i'}\larr 1-S_{i'}$，$i\larr i'$。求最后 $w$ 期望值。

枚举数对 $(u,v)$，分别考虑 $i=u,i'=v$ 的期望步骤数，将这个期望乘上 $|u-v|$ 加到总期望即可。对于一个状态，我们记下 $S_u$、$S_v$ 的值，而 $u$、$v$ 以外的点互相平等，只用记录 $1$ 的个数，以及指针位置，其中非 $u$、$v$ 的点压到一起。这样一共有 $3\times 2^2(n-1)$ 种状态，答案为 $(S_u,S_v,\sum_{i=1}^n[i\neq u∧i\neq v]S_i,i')$ 随机游走到 $(0,0,0,\dots)$ 的期望次数，高斯消元即可。

Atcoder Grand Contest

DP 篇

ACG020E Encoding Subsets。

定义合法变化为：

$0\rarr 0,1\rarr 1$ 合法。

$A\rarr B$、$C\rarr D$ 合法，则 $AB\rarr CD$ 合法。

g13d

g17f

g12f

g08

g20f

---

g17c

g07c

g17e

g18f

g04f

r153f

r152f

---

g18e

r163f

r154f

---

g21e

g21f

g22f

---

后记

$\huge\sf{\color{#F00}T\color{#0C0}E\color{#FFA500}T\color{#F0F}R\color{#0EE}I\color{#EE0}S}\ Hot\ News!$

$\sf Wow!\ Player\ \text{Z\color{#F00}KYGT1}\ competed\ in$

$\sf 40\ Lines\ Challenge,\ placed\ a\ VERTICAL$

$\sf{\color{#0EE}I-Block}\ and\ gained\ +19 \stackrel{\ \ \ \ \ \ \color{#F0F}T-SPIN}{DOUBLE}s$

$\sf taking\ lines\ cleared\ 38$

$\huge\sf Share\ it!$