复杂度鉴赏_LCA

复杂度鉴赏

诸如 $2^{\sqrt n}$ 之类的奇怪复杂度，这种题目可能有两种情况：

• 某些自然成立的不等式，导致实际需要枚举的量并不多，除法或开根出现在指数上带来极大的复杂度优化。
• 两种不同复杂度的算法皆能解决这个问题，平衡后得到一个奇怪的复杂度。

#T241115E. 【昊天塔】对半博弈

一开始给定一个固定的数组 $\{a\}$，长度为 $2^L$，值域为 $[1, n]$。另有一个长度为 $n$ 的数组 $\{val\}$，在其中每个位置填上一个 $[1, m]$ 中的整数，显然有 $m^n$ 种方案。

Alice 和 Bob 轮流对 $\{a\}$ 进行操作，每次将 $\{a\}$ 剪成左右长度相等的两半，然后选一半丢弃，另一半保留，直到最后剩下一个数 $x$，游戏的得分即为 $val[x]$。Alice 先手，她希望最终得分尽量大，而 Bob 希望得分尽量小。

现在，想知道对于所有 $m^n$ 种填 $val$ 的方案，最终得分总和会是多少？答案对 $10^9 + 7$ 取模。

$n\le 32,T\le12,L\le 5,m\le 10^9$。

来规范一下题意：我们有一个决策树，从上往下第奇数层取儿子的 $\max$，偶数层取儿子的 $\min$，叶子权值是 $val_{a_i}$。

求所有 $val$ 对应的方案的根的权值和。

考虑 $a$ 互不相同，此时相当于 $a_i=i$，也就是每个叶子独立随机，此时我们有状态 $f_{x,i}$ 表示节点 $x$ 权值为 $i$ 的概率，转移是设 $g,h$ 为 $f$ 的前缀/后缀和，则取 $\min$ 就是 $f_{ls,i}g_{rs,i}+f_{rs,i}g_{ls,i-1}$，$\max$ 同理。

使用经典的 $0/1$ 原理，显然只要对 $k\in[0,2^L]$ 求出叶子中有 $k$ 个 $1$ 的所有情况中有多少种根是 $1$，就可以轻松实现给定 $val$ 可重集，求出答案，这样就把计算拆分为了 $0/1$ 原理和计算可重集。

但这个形式是难以 $\rm dp$ 的，其关键在于绑定这件事我们无法约束，但我们发现：绑定大小 $>1$ 的组至多 $n/2$ 个，我们可以直接枚举这些组的 $0/1$ 取值，剩下的单点来 $\rm dp$。

注意这里特殊的 $0/1$ 原理：一个大小为 $x$ 的等价类为 $1$，我们应当仅仅将其视为一个 $1$，这是因为它们已经强制绑在了一起，我们实际的自由度只有 $m^n$。

可重集的系数是什么呢？考虑 $0/1$ 原理划分为了 $\gt v$ 和 $\le v$，且有 $x$ 个 $\gt v$ 的，$y$ 个 $\le v$ 的，则系数显然为 $v^y(m-v)^x$，虽然我们并不会对于 $m=10^9$ 算这个，但是这显然是关于 $m$ 的 $\mathcal O(n)$ 次多项式，插值解决即可。

复杂度 $\mathcal O(2^{2^{L/2}}\text{poly}(2^L))$。

CF1149D Abandoning roads

一张 $n$ 个点 $m$ 条边的无向联通图，只有 $a,b$ 两种边权（$a<b$），对于每个 $i$，求图中所有的最小生成树中，从 $1$ 到 $i$ 距离的最小值。

$n\le 70,m\le 200$。

只有两种边权，我们当然考虑最小生成树有什么性质。

先加入所有的 $a$ 边形成若干连通块，我们发现，在行走”最短路“的过程中，我们通过 $b$ 边离开一个连通块后不可能再通过 $b$ 边回到之前走过的连通块，否则这条路一定不在最小生成树上，而满足了上述条件显然一定在最小生成树上。

在最短路的过程中额外记录 $S$ 表示走过了哪些连通块，我们得到了一个 $2^nm\log m$ 的做法。

但我们发现有些连通块太浪费了，具体来说，大小为 $1,2$ 的连通块显然没必要记录，大小为 $3$ 的连通块内部最多 $2a$，外部最少 $2b$，所以我们只需记录特殊的 $n/4$ 个连通块。

注意我们必须删掉同一连通块内的 $b$ 边。

复杂度 $2^{n/4}m\log m$。

Gym102978e Edge Subsets

一个无向图，每条边满足 $v-u=A\vee v-u=B$。

求匹配个数。

$n\le 200,m\le 2n,A<B$。

超牛预判，前一天刚写下了题目描述第二天被云斗搬了，但是鉴于完全看不懂题解只能说被透了一半，在知道大方向的情况下自己做出。

若 $\gcd(A,B)>1$ 显然可以按 $\bmod\ g$ 拆分成 $g$ 个子问题处理，所以默认 $\gcd(A,B)=1$。

我们首先会解决 $B\le 20$ 的情况，直接顺着扫，状压之前 $B$ 个有没有选即可，复杂度 $n2^B$。

若 $B>20$，则我们以按 $\bmod \ B$ 划分等价类，则等价类的大小很小。

直接状压这个等价类内的元素是否选择，然后按 (x+=A)%=B 的顺序处理这些等价类，像网格图的轮廓线 $\rm dp$ 一样按格处理即可。

由于我们要转一个圈，我们只能先钦定首个等价类内的元素“内部以及与之前”占用了 $S$，最后推一轮回来把 $f_S$ 贡献给答案，复杂度 $n2^{2(n/B)}$。

平衡后可以平衡到 $n2^{\sqrt {2n}}$。

团计数 CCPC Online 2023 C. Clique Challenge QOJ7514

给定图，问有多少个团。

$n,m\le 1000$。

在 $m≈ n^2$ 时，对团计数可以对补图使用 $2^{n/2}$ 的独立集计数：令 $v=\min S$，则 $f(S)=f(S\setminus \{v\})+f(S\setminus(\{v\}\cup N(v)))$，当 $|S|\le n/2$ 时 $S$ 中的点都 $>n/2$，则我们可以记搜，$|S|>n/2$ 时分支最多 $2^{n/2}$ 个。

考虑类似于三元环计数的小度连大度，这种连边方式可以证明新图度数 $\le \sqrt{2m}$（小度显然出度 $\le B$，大度最多连 $\frac{\sum d}B$ 个）。

考虑用团中度数最小的点（相同度数钦定一个顺序）来统计整个团。

于是我们找到了一个规模为 $n=\sqrt {2m}$ 的问题，使用上面的 $2^{n/2}$ 算法解决即可。

复杂度在图是一个 $\sqrt {2m}$ 的团最大，为 $\sqrt m2^{\sqrt{2m}/2}$。

实现上当然没有必要写成搜的形式，后一半点直接对集合 $\rm dp$，然后枚举前一半点选不选求答案。

P9318 [EGOI 2022] Lego Wall / 乐高墙

你要用 $1\times1$ 和 $1\times 2$ 密铺 $n\times m$（注意没有 $2\times 1$ 的竖条），且若上下紧挨的积木之间连边，该图只能有一个连通块。

计数方案。

$n\times m\le 5\times 10^5,n,m\ge 2$。

$n,m$ 这么大，我们当然要先想出 $\rm poly$ 做法。

考虑经典的容斥，我们发现不合法的图，总是满足每个连通块是一个上下顶满边界的长方形，所以我们从左往右 $\rm dp$，设 $f_{i}$ 表示前 $i$ 列合法的情况数，$g_i$ 表示 $n\times i$ 的平面随便铺的方案数，则：

f_i=g_i-\sum_{1\le j

复杂度 $n^2m$。

平衡复杂度，注意这里是 $n,m$ 互相抗衡而不是固定 $n$ 调节块长 $B$，所以我们直接将 $m$ 写成 $S/n$ 然后将 $n$ 视作“块长”来调节即可，$nS=S^2/n^2\to n=S^{1/3},m=S^{2/3}$，复杂度为 $S^{4/3}$，可以通过。

CF2002G Lattice Optimizing

一张 $n\times n$ 的网格图，每条边上有数字，你只能往下和右走，从 $(1,1)$ 到达 $(n,n)$，找出 $mex$ 最大的路径。

$n\le 20$。

虽然 $n$ 只有 $20$，但是路径上有 $2n-1$ 个数，直接集合 dp 是 $4^n$ 的。

考虑 meet-in-the-middle，以地图副对角线劈开，每边有 $2^n$ 个数，你发现合并需要求超集/子集，复杂度又变得奇怪起来了。

你发现只需要一边求子集，另一边直接 query，这太不公平了！于是我们以 $\frac 2 3n,\frac 4 3n$ 分开，用 $\frac 2 3 n$ 那边求子集，复杂度 $2^{\frac 4 3 n}$。

UOJ Round #28 A 偷吃蛋糕

超难爆搜，无法战胜。

关键是证明需要动用 zak，过于困难了。