Pig's DP

· · 算法·理论

Pig 的 DP 题！然而做了也不会像 Pig 一样聪明（

可能不会按照难度排序，但大多数 CF 题都有难度标签，可以参考。

可以在博客园查看。

\text{TODO LIST : P3780 P6596}

一般列入 TODO LIST 的应该都是懒得写题解的题了。

\text {SIZE} : 79.9\ \text{KB}(2024/2/27)

普通 dp

一些纯思维的 dp，可能比较套路，也有可能不好分类所以放在这里。

CF1271D Portals

Difficulty : 2100

对于一个 u，记录 lt_u 表示最大的能够到达它的点 v，考虑按照 lt 对 1 到 n 进行排序。

同时开一个指针 p，表示当前可控制的城堡。

令 dp_{i,j} 表示到第 i 个城堡剩下 j 个士兵的最大得分。

如果到了 i 什么都不做，那么显然 dp_{i,j+b_i}\gets dp_{i-1,j}；然后你继续移动指针 p，只要 lt_p=i，即可转移 dp_{i,j}\gets dp_{i,j+1}+c_p。

不难看出 c_i 为排序后城堡 i 的价值，和题面中的不一样。

CF213C Relay Race

Difficulty : 2000

按照套路，跑两次路线就相当于两个人一起从 (1,1) 出发。

然后两个人在某一时刻一定不在对方的历史路线上，因为步数相等。

步数相等还有一个好处，就是可以用来做状态，如果已知步数 i，两个人走到的行数 j,k，那么两个人的坐标也是可以算的，显然就是 (j,i-j+1) 以及 (k,i-k+1)。

于是令 dp_{i,j,k} 表示上述状态，则：

dp_{i,j,k}\gets dp_{i-1,j,k} dp_{i,j,k}\gets dp_{i-1,j-1,k} dp_{i,j,k}\gets dp_{i-1,j,k-1} dp_{i,j,k}\gets dp_{i-1,j-1,k-1}

正常做的话空间 O(n^3)，有点危险。

然后第一维是可以滚掉的，所以空间 O(n^2)，时间 O(n^3)。

CF459E Pashmak and Graph

Difficulty : 1900

考虑一般的不降子段咋做，n\le 3\times 10^5。

令 dp_i 为以 i 结尾连续不降子段最长长度：

dp_i\gets dp_{i-1}+[a_{i-1}\le a_i]

当然也有一种方法，将 a_i 从小到大排序，记排序后 a_i 在原数组中对应下标为 p_i，dp_{p_{i}}\gets dp_{p_{i}-1}+1，答案为 \max\{dp_i\}。

这里用第二种方法，放到图上。

先按照边权从小到大排序，然后考虑转移。

因为题目要求严格递增，而直接转移的话可能会使得连在一起相同权值的边也被算进去，所以要先把相同权值的边对应两点的 dp 值存下来，然后用这个数组转移 dp 即可。

CF337D Book of Evil

Difficulty : 2000

感觉这是前面最思维的一道题（？

以下有怪物的点记为关键点。

记录 u 子树内关键点离 u 最远和次远距离（两个关键点不在 u 的同一个儿子的子树内），记为 dp_{u,0/1}。

考虑从叶子向根转移，显然有：

然后令 dis_u 为 u 的子树外关键点距离 u 的最远距离，考虑从根到叶子转移：

然后最后遍历每一个节点，如果当前节点为根节点，只需要满足 dp_{u,0}\le d 即可对答案贡献；如果当前节点不为根节点，需要满足 dp_{u,0},dis_u\le d。

复杂度 O(n)。

CF710E Generate a String

Difficulty : 2000

首先如果加了一个字符，然后再删肯定不优。

于是只有倍长后才能删去一个字符，此时长度一定为奇数。

所以 f_i\gets \min\{f_{i-1}+x,f_{i/2}+y\},2\mid i 或者 f_i\gets \min\{f_{i-1}+x,f_{(i+1)/2}+y+x\},2\nmid i。

ARC065D シャッフル / Shuffling

Difficulty : 2652

鬼知道这个难度是怎么搞出来的……不过这题确实挺神的。

设 $f_{i,j}$ 表示考虑前 $i$ 位填了 $j$ 个 $1$ 的方案数。 显然有 $f_{i,j}\gets f_{i-1,j-1}+f_{i-1,j}$，关键是转移上下界如何确定，因为有些地方是不能放 $1$ 的。 于是可以预处理出每个 $i$，能随意排列到的最右端点 $r_i$；以及每个前缀 $1$ 的个数 $c_i$。 则转移中 $j$ 的下界的话你当然希望前 $i$ 个位尽量放 $0$，所以先把 $i$ 到 $r_i$ 尽量全放 $1$，于是 $l_j=\max\{0,i-(r_i-c_{r_i})\}$。 对于上界，你也当然希望前 $i$ 位尽量放 $1$，所以先把 $r_{c_i}$ 个 $1$ 都放 $i$ 里面，于是 $r_i=\min\{i,r_{c_i}\}$。 [AC 记录](https://atcoder.jp/contests/arc065/submissions/35464170) ### [CF883I Photo Processing](https://www.luogu.com.cn/problem/CF883I) Difficulty : 1900 $dp$ 与二分结合。 最大价值最小，考虑二分答案。 把 $a_i$ 从小到大排序的话，你会发现你选的组一定是连续的，不然不优。 于是令 $dp_i$ 表示仅考虑 $1$ 到 $i$ 一共 $i$ 个数是否有可行的分组。 那么 $dp_i\gets dp_{j}(j\in\{0,1,...,i-m\},a_i-a_{j+1}\le \lim)$。 $lim$ 即为你二分的答案。 但这样显然过不了，考虑优化，首先你发现最小的 $j$ 使得 $a_i-a_j\le\lim$ 是单调不降的，$j$ 的上限也是单增的，滑动窗口即可。 就是搞一个双向队列，如果 $dp_{i-m}$ 为 `true` 的话就从右边加进来 $i-m$，然后一直弹出左边不符合的（即不满足 $a_i-a_{j+1}\le lim$），最后如果队列里面还剩下可以转移的位置那么 $dp_i=1$ 了。 由于左指针的移动次数最多 $O(n)$，所以 check 的复杂度是 $O(n)$ 的。 复杂度 $O(n\log n)$。 ### [CF1187E Tree Painting](https://www.luogu.com.cn/problem/CF1187E) Difficulty : 2100 无脑题，以后尽量避免点进这种题目，否则会变笨。 设第一个黑点为树的根节点，当「根」确定了不难发现同深度的染色互不干扰，因为它们的父亲都染了色，于是它们不在一个连通块中。 不难发现染 $u$ 的权值为 $\mid subtree(u)\mid

然后换根 dp 即可。

POI2006 MIS-Teddies

简单 dp 题。

我们只关心个数和最后 2 位，大力设六维 f_{i,j,p,q,x,y}，每次转移枚举 4 种情况，判断是否合法然后贡献即可。

复杂度 O(n^4b^3)，b 为泰迪熊的种数即 4。可能需要滚动数组，反正我没有高超的卡常技巧。

CF852H Bob and stages

考虑到 n 和 k 都很小，可以先将所有点对于 x,y 坐标排序，枚举答案凸包最左边那个点 p。然后设 f_{i,j} 表示走了 i 步，目前位于 j 点的最大面积，答案就是 f_{k,p}。

考虑从 f_{i-1,x} 转移到 f_{i,y}，此时 dp 受如下限制影响：

由于任意的转移前后都满足限制，考虑将凸包拆分成若干个以 p 为顶点的三角形，每次相当于加入以 p,x,y 为顶点的三角形，如果我们是逆时针加入点，转换限制如下：

第一个限制满足了凸多边形的性质，第二个限制归纳满足了凸包内部没有点的限制。

但是此时又有一个问题：如何确定 x 转移过来的直线的斜率。一个简单的想法是再加一维状态 k 表示第 i 步是由 k 走到 j，但是复杂度 O(n^4k)，寄了。

不妨优化转移，考虑对转移的边进行极角排序，那么后面的边就一定能从前面的边转移过来了。于是排序后依次枚举转移边，再枚举步数，复杂度就是 O(n^3k) 的了，足以通过本题。

有一个细节问题，就是 p\to x 向量如果 x 坐标为 0 且 y<0，那么极角排序时会把它放到开头，此时对于所有点排序时 x 坐标相同应将 y 坐标大的放前面，否则转移不到。

状压 dp

CF839E Mother of Dragons

Difficulty : 2700

发现若 u,v 不通过一条边联通且 \sum\limits_{w\in N(u)}s_w\ge \sum\limits_{w\in N(v)}s_w，那么把 s_v 加给 s_u 一定不劣。

所以最后答案一定是一个连通完全子图，设其大小为 m，那么答案就是 \dbinom{m}{2}\left(\dfrac{k}{m}\right)^2。

不难发现这东西关于 m 单调递增，所以求出最大团大小即可。

典型的做法是折半，可以 O(n) 判断一个点集的导出子图是否是团，枚举半边的一个团 S ，另一半预处理 f(T) 表示点集 T 导出子图中的最大团大小，然后求出半边点都能连到的另一半的点的集合 T，求 |S|+f(T) 的最大值即可。

复杂度 O(n2^{\frac{n}{2}})。

P2150 [NOI2015] 寿司晚宴

典。

考虑 n\le 30，其以内只有 10 个质数，于是考虑状压。

显然 $dp_{i,j,k\ or\ st(i)}\gets dp_{i-1,j,k}\ (st(i)\ and\ j\ =\ 0)$ 或者 $dp_{i,j\ or\ st(i),k}\gets dp_{i-1,j,k}(st(i)\ and\ k\ =\ 0)$。 然后可以滚动数组，但是没有必要，反正过不了，复杂度 $O(2^{20}n)$。 然后考虑 $n\le 500$，此时 $\sqrt{n}<30$，这表明除了 $\le 30$ 的质因子之外，$n$ 可能有且仅有 $1$ 个大于 $30$ 的大质因子。 $dp$ 含义不变，记录 $dp1,dp2$ 分别表示这个大质因子在分别两个人那边的方案数量。 求出 $2$ 到 $n$ 每个数的大质因子，然后按其升序排序，以便分段考虑。 在大质因子都相同的一段内，$dp1,dp2$ 的转移与上述 $dp$ 类似，不过你只能选定一个人进行转移，比如如果你选 $dp1_{i,j,k\ or\ st(i)}\gets dp1_{i,j,k}(st(i)\ and\ j=0)$，那么 $dp2$ 就必须把数搞到 $j$ 上面，原因可由 $dp1,dp2$ 的定义得到。 然后如果跨段的话更新 $dp_{i,j,k}=dp1_{i,j,k}+dp2_{i,j,k}-dp_{pr,j,k}$（$pr$ 为上一段末尾的下标），即减去两个人都没有选大质因子的情况。 滚掉第一维，最后的答案就是 $\sum dp_{j,k}$。 ### [CF510D Fox And Jumping](https://www.luogu.com.cn/problem/CF510D) Difficulty : 1900 ~~还是典。~~ 由于 $2\times 3\times 5\times 7\times 11\times 13\times 17\times 19\times 23=223092870$，所以 $10^9$ 以内的数其质因子不超过 $9$ 个。 所以如果我们先钦定选一张卡 $k$ 的话，只用考虑剩下所有卡中对于被 $k$ 这不超过 $9$ 个质因子的整除情况。 因为在选卡牌的过程中 $\gcd$ 单调不增，所以令 $dp_{st}$ 表示当前 $\gcd$ 状态为 $st$ 的最小代价，首先 $dp_{st_i}=c_i$（$st_i$ 为 $i$ 对于钦定卡牌 $k$ 的质因数状态）。 所以如果选了 $i$ 卡牌，当前质因数状态为 $s$，那么： $dp_{s\&st_i}\gets dp_s+c_i

求质因子的话根号分解质因数即可，总复杂度 O(n\sqrt m+2^9n^2)，m 为最大的 l_i。

SDOI2009 Bill的挑战

忽略容斥，无脑状压。预处理出 tr_{i,j}(i\le len,j\le 25) 表示 T 第 i 位填 j 能够匹配的状态（这里的“状态”指 0\to 2^n-1 的二进制数）。令 dp_{i,st} 表示第 i 位填完，匹配状态位 st 的方案数，dp_{0,2^n-1}=1。

复杂度 $O(26m2^n)$，$m$ 为字符串长度。 ### [CF11D A Simple Task](https://www.luogu.com.cn/problem/CF11D) Difficulty : 2200 经典状压。 记 $dp_{i,st}$ 表示走到点 $i$，经过点的状态为 $st$ 的方案数。 显然初始时 $dp_{i,2^i}=1$。为了防止算重，我们钦定 $st$ 状态中最低的那一位即 `lowbit(st)` 为环的起点， 对于一条边 $(u,v)$，$dp_{v,st|2^v}\gets dp_{u,st}(v\notin st)$，否则如果 $2^v=lowbit(st)$，就统计答案。 由于会算重两个点组成的环的情况，所以答案要减去 $m$。 由于一个环顺时针逆时针被算了两次，所以答案还要除 $2$。 复杂度 $O(2^nm)$ 或者 $O(2^nn^2)$。 ### [Xmas Contest 2021 D Determinant?](https://www.luogu.com.cn/problem/AT_xmascon21_d) 由 [Amitsur-Levitzki 定理](https://zhuanlan.zhihu.com/p/513568180)，当 $n\ge 2k$ 时，答案为 $0$ 矩阵。 否则我们考虑答案矩阵的某一位 $b_{i,j}$，其必然由某些路径 $i=p_0\to p_1\to\ \cdots \to p_n=j$ 贡献而来，一条路径的贡献为 $\text{sgn}(\sigma)\cdot \prod\limits_{i=1}^nA_{\sigma(i),p_{i-1},p_{i}}$。 于是直接 dp，类似状压求行列式，记录当前 $\sigma$ 中的 $A$ 矩阵集合，dp 的值为一个矩阵，表示目前的 $\text{sgn}(\sigma)\prod A_{\sigma(i)}$。每次转移进行一次矩阵乘法。复杂度 $O(2^nnk^3)=O(4^kk^4)$。 ### [PKUSC2018 最大前缀和](https://www.luogu.com.cn/problem/P5369) 这个期望显然是诈骗，即统计每种排列最大前缀和之和。 对于某个排列 $a$，令 $s(l,r)=\sum\limits_{k=l}^ra_k$。考虑前缀 $[1,i]$ 成为答案的**充要条件**： - $\forall 1<j\le i,s(j,i)\ge 0$，否则可以去掉这段。 - $\forall j>i,s(i+1,j)<0$，否则加上这段不劣（钦定取的是**最大并且最靠后**的前缀）。 那么可以考虑状压，设 $f_S$ 为选择 $S$ 这个集合作为 $[i+1,n]$ 并且满足第 $2$ 个条件的方案数，设 $g_S$ 为选择 $S$ 这个集合作为 $[2,i]$ 并且满足第 $1$ 个条件的方案数。转移的话就考虑哪个数塞到开头/结尾即可。 统计答案时枚举第 $1$ 位填 $a_i$，然后枚举集合 $S$ 作为合法的前缀，计算方案数用 $g_S$ 乘 $f_{U\setminus (S\cup\{i\})}$ 即可，即： $$\text{ans}=\sum\limits_{i=1}^n\sum\limits_{S\subseteq U\setminus\{i\}}\left(\sum\limits_{k\in S\cup\{i\}}a_k\right)g_Sf_{U\setminus(S\cup \{i\})}$$ 复杂度 $O(n2^n)$。 ### [ZJOI2015 地震后的幻想乡](https://www.luogu.com.cn/problem/P3343) Hint 是 $n$ 个 $[0,1]$ 之间均匀随机分布的数的第 $k$ 小值的期望为 $\frac{k}{n+1}$，证明可见[这篇博客](https://www.cnblogs.com/penth/p/9743303.html)。 考虑 Kruskal 求最小生成树的过程。从小到大加入每条边，当加入第 $i$ 一条边时整张图联通了，那么 $w_i$ 就是生成树上边权最大值。 这启示我们钦定一个边集 $S$，包含了前 $|S|$ 小的边权，加入第 $|S|$ 条边时**整张图刚好联通**。由提示知道此时 $S$ 对答案的贡献为 $\frac{|S|}{m+1}$。考虑统计大小为 $i$ 的符合 $|S|=i$ 的方案数，除以总方案 $\dbinom{m}{i}$ 即可得到概率。 难搞的限制在于加入第 $i$ 条边时恰好联通，考虑容斥，转化成加入第 $i$ 条边 $S_i$ 前不连通的方案数减去加入第 $i$ 条边后不连通的方案数。于是概率就变成了加入 $S_i$ 前不连通的概率减去加入 $S_i$ 后不连通的概率。 于是只需要求出加入 $S_i$ 后**不连通的方案数**。考虑 dp，设 $f_{T,i}$ 为考虑点集 $T$，其中连了 $i$ 条边，点集内**不连通**的方案数；为了方便转移，维护 $g_{T,i}$ 为考虑点集 $T$，连 $i$ 条边，**联通**的方案数。显然有 $f_{T,i}+g_{T,i}=\dbinom{d_T}{i}$，$d_T$ 表示点集 $T$ 导出子图中边的个数，即 $|E(G(T))|$。 考虑转移，由于不能联通，枚举一个连通块 $T'\subsetneqq T$ 及其内部边数，连通块外任意连边，那么： $$f_{S,i}=\sum\limits_{T'\subsetneqq T}\sum\limits_{j=0}^{d_{T'}}g_{T',j}\dbinom{d_{T\setminus T'}}{i-j}$$ 但是这样做有个问题，对于对于不同的连通块可能会算重。所以在 $T'$ 中钦定一个点 $k\in T$，$k\in T'$。 答案就是 $\sum\limits_{k=1}^{m+1}\frac{k}{m+1}\left(\dfrac{f_{U,k-1}}{\dbinom{m}{k-1}}-\dfrac{f_{U,k}}{\dbinom{m}{k}}\right)$，$U$ 为全集。可以化简但没必要，复杂度 $O(3^nm^2)$。 ### [CF1193A Amusement Park](https://www.luogu.com.cn/problem/CF1193A) 发现一个 DAG 所有边反转后仍然是 DAG，所以一个反转了 $c$ 次的反转方案唯一对应了一个反转了 $m-c$ 次的方案。两种方贡献案之和为 $m$，所以设 $s$ 为给无向图定向成为 DAG 的方案数，答案就是 $\frac{s\times m}{2}$。 于是问题转化为求给一张无向图边定向，使得定向后成为 DAG 的方案数。考虑状压 dp，令 $f_S$ 为给点集 $S$ 的导出子图定向后为 DAG 的方案数。 考虑 DAG 中一定有出度为 $0$ 的独立集，同时删去这个集合后图仍为 DAG，所以枚举独立集 $T$，钦定其出度为 $0$： $$f_S=\sum\limits_{T\subset S,T\neq \varnothing}f_{S\setminus T}\cdot g(|T|)[T\in \text{independent set}]$$ $g(n)$ 为容斥系数，因为会算重。由于一个大小为 $n$ 的点集 $T$ 会被它的每个非空子集计算一次，而我们要求 $T$ 的贡献恰好为 $1$： $$1=\sum\limits_{i=1}^n\dbinom{n}{i}g(i)$$ 大眼观察得：$g(1)=1,g(2)=-1,g(3)=1,\cdots$。我们猜测 $g(n)=(-1)^{n_+1}$： $$\begin{aligned}\sum\limits_{i=1}^m\dbinom{n}{i}(-1)^{i+1}&=-\left(\sum\limits_{i=0}^{n}\dbinom{n}{i}(-1)^i-1\right)\\&=-\left((-1+1)^n-1\right)=1\end{aligned}$$ 所以取 $g(n)=(-1)^{n+1}$ 即可： $$f_S=\sum\limits_{T\subset S,T\neq \varnothing}(-1)^{|T|+1}f_{S\setminus T}[T\in \text{independent set}]$$ 暴力算是 $O(3^n)$ 的，在线做子集卷积即可达到 $O(n^22^n)$。 ## 计数 | 期望 | 概率 dp ### [CF895C Square Subsets](https://www.luogu.com.cn/problem/CF895C) Difficulty : 2000 $dp$ 与排列组合/数学结合。 首先看到 $a_i\le 70$，并且平方数仅考虑质因数个数的奇偶性，所以考虑压缩质因数状态。打表发现 $70$ 以内只有 $19$ 个质数，于是可做。 令 $dp_{i,st}(i\in\{1,2,...,70\},st\in\{0,1,...,2^{19}-1\})$ 表示当前考虑到 $i$，且选完质因数个数奇偶状态变为 $st$ 的方案数。 于是如果选奇数个 $i$，则 $dp_{i,st}\gets dp_{lt,st\ xor\ st(i)}\times(C_{c(i)}^{1}+C_{c(i)}^{3}+C_{c(i)}^{5}+...)$；如果选偶数个 $i$，那么 $dp_{i,st}\gets dp_{lt,st}\times(C_{c(i)}^{2}+C_{c(i)}^{4}+C_{c(i)}^{6}+...) 注意到 $C_{c(i)}^{1}+C_{c(i)}^{3}+C_{c(i)}^{5}+...=C_{c(i)}^{2}+C_{c(i)}^{4}+C_{c(i)}^{6}+...=2^{c(i)-1}$，于是： $dp_{i,st}\gets (dp_{lt,st\ xor\ st(i)}+dp_{lt,st})\times 2^{c(i)-1}

然后答案就是 dp_{lt, 0}-1，去掉全都不取的情况。

滚一滚，空间 O(2^w+n)，时间 O(w2^w)，w=19。

CF893E Counting Arrays

Difficulty : 2000

还是 dp 和数学结合。

根据小学套路，前 y-1 个符号可以先忽略，留在第 y 个调整，所以符号共有 2^{y-1} 种。

所以以下只需要考虑正整数的情况，发现由于乘积 \le 10^6，最多只能填 19 个非 1 的正整数，于是考虑 dp。

令 dp_{i,j}(i\le19,j\le10^6) 表示长度为 i 的不含 1 的正整数列，乘积为 j 的方案数。

显然有：

dp_{i,j}=\sum_{k\mid j,k<j}dp_{i-1,k}

注意到不好枚举每个数的因数，我们考虑枚举每个因数的倍数，那复杂度就变成了一个调和级数。

考虑把 1 加进去，枚举非 1 项个数 i，将 y-i 个 1 插进 i+1 个空里面，和分组同理，方案数为 \dbinom{y-i+i+1-1}{i+1-1}=\dbinom{y}{i}。

于是答案就是：

2^{y-1}\sum_{i=1}^{\min(y,19)}\dbinom{y}{i}dp_{i,x}

复杂度 O(n\log^2{n}+q\log{n})。

NOIP2016 提高组 换教室

期望好题。

考虑到申请次数有限制，那就需要纳入 dp 状态了。

令 dp_{i,j,0/1} 表示考虑前 i 个时刻，包含 i 在内总共申请了 j 次，第 i 次申/不申请的最小期望。

然后由于转移时从 u 走到 v 一定是走最短路最优，所以可以先用 floyd O(v^3) 预处理出任意两个点的最短路。

考虑转移：

若 i 时刻不申请，转移 dp_{i,j,0}，若 i-1 时刻也不申请，dp_{i,j,0}\gets dp_{i-1,j,0}+dis_{c_i,c_{i-1}}；若第 i-1 时刻申请了，根据概率知识有 dp_{i,j,0} \gets dp_{i-1,j,1}+(1-p_{i-1})dis_{c_i,c_{i-1}}+p_{i-1}dis_{c_i,d_{i-1}}。

同理，若 i 时刻申请，转移 dp_{i,j,1}，若 i-1 时刻不申请，dp_{i,j,1}\gets dp_{i,j-1,0}+(1-p_i)dis_{c_i,c_{i-1}}+p_idis_{d_i,c_{i-1}}，若 i-1 时刻申请了，则需要分四种情况：dp_{i,j,1}\gets dp_{i,j-1,1}+(1-p_i)(1-p_{i-1})dis_{c_i,c_{i-1}}+(1-p_i)p_{i-1}dis_{c_i,d_{i-1}}+(1-p_{i-1})p_idis_{d_i,c_{i-1}}+p_ip_{i-1}dis_{d_i,d_{i-1}}。

初始状态 dp_{1,0,0}=dp_{1,1,1}=0。

复杂度 O(nm+v^3)。

SHOI2012 随机树

期望 dp。

考虑第 1 个询问，我们令 f_i 表示叶子节点数为 i 时，叶节点的平均深度期望。然后我们随机抽一个叶子节点进行展开，此时对叶子节点深度和的贡献为 2(f_i+1)-f_i=f_i+2，即 f_{i+1}=\frac{if_i+f_i-2}{i+1}=f_i-\frac{2}{i+1}，初始时 f_1=0。

再考虑第 2 个询问。考虑到 \mathbb{E(x)=\sum p(i)i}，p(i) 为 n 个叶子节点，树深度为 i 的概率，考虑一个后缀和，我们设 g_{i,j} 为 i 个叶子节点，树的深度 dep\ge j 的概率，答案即为 \sum\limits_{i=1}^{n}g_{n,i}。

对于转移，我们可以枚举左右子树大小，即：

g_{i,j}=\frac{1}{i-1}\sum\limits_{k=1}^{i-1}g_{k,j-1}+g_{i-k,j-1}-g_{k,j-1}\times g_{i-k,j-1}

因为会有算重（两个子树深度均大于等于 j-1）的情况，转移还减去了 g_{k,j-1}\times g_{i-k,j-1}。

复杂度 O(n^3)。

Luogu3412 仓鼠找sugar II

设 f_u 表示从 u\to fa(u) 的期望步数，g_u 为 fa(u)\to u 的期望步数，d_u 为 u 的度数。

那么显然有：

f_u=\frac{1}{d_u}\left(1+\sum\limits_{v\in son(u)}(1+f_v+f_u)\right)

移项后得到 f_u=d_u+\sum\limits_{v\in son(u)}{f_v}。

求 g_u 的话要分两类：

g_u=\frac{1}{d_{fa(u)}}\left(1+(1+g_{fa(u)}+g_u)+\sum\limits_{v\in son(fa(u))\setminus \{u\}}(1+f_v+g_u)\right) g_u=\frac{1}{d_{fa(u)}}\left(1+\sum\limits_{v\in son(fa(u))\setminus\{u\}}(1+f_v+g_u)\right)

由于 g_{\text{root}}=0，移项后均能得到 g_{u}=f_{fa(u)}+g_{fa(u)}-f_u。

然后就可以预处理出 f,g 了。

考虑所有路径 u\to v，统计从 u 走到 v 的期望步数，再除去 n^2。一条 u\to v 的路径，将其贡献与 v\to u 的路径合并。记一条边 e:(u, fa(u)) 的权值为 w_e=f_u+g_u，\text{lca}(u,v) 为 k，就变成了经典问题。注意到：

\begin{aligned}&\sum\limits_{(u,v)}\left(\sum\limits_{p\in [u\to k]\setminus \{k\}}f_p+\sum\limits_{p\in [k\to v]\setminus \{k\}}g_p\right)\\=&\sum\limits_{u,v(\text{无序})}\left(\sum\limits_{p\in [u\to v]}(f_p+g_p)-f_k-g_k\right)\\=&\sum\limits_{e:(u, fa(u))}w_esz_u\left(n-sz_u\right)\end{aligned}

第 2 步为考虑每条边对答案的贡献，即为穿过这条边的路径条数。

然后就很好做了。复杂度 O(n)。

CF605E Intergalaxy Trips

Difficulty : 2700

设 dp_{i} 为 i 到 n （不留在 i 原地）的期望天数，显然 dp_n=0，并考虑两个简单的结论：

这和最短路很像，启示使用类似求最短路的方法求解原问题，虽然我知道直接这样写出来很蠢。

考虑现在转移 i，i 出边形成的邻域 dp 值从小按大排序形成序列 a：

所以转移：

dp_i=\sum\limits_{j=1}^m\dfrac{dp_{a_j}}{1-\prod\limits_{k=1}^{n}(1-p_{a_j,a_k})}p_{i,a_j}\prod\limits_{k=1}^{j-1}(1-p_{i,a_k})+1

CF398B Painting The Wall

首先可以先去掉已经符合条件的行或者列，然后设 dp_{i,j} 表示还剩 i 行 j 列的操作次数的期望。

那么可以分情况讨论：

我们发现转移过程有自己转移自己的情况，对于这种操作无限的题目可以求解方程，在此题中我们求出 dp_{i,j} 的转移式即可。

移项后得：

dp_{i,j}=\dfrac{ijdp_{i-1,j-1}+i(n-j)dp_{i-1,j}+(n-i)jdp_{i,j-1}+n^2}{n^2-(n-i)(n-j)} ### [CF123E Maze](https://www.luogu.com.cn/problem/CF123E) Difficulty : 2500 考虑 $u$ 做起点时，树上每个点对答案的贡献。 先把 $u$ 当作根，然后假设当前终点为 $v$，先计算这条路径的期望长度： - 对于 $v$ 子树内的边，显然不会计入路径当中，贡献为 $0$。 - 对于 $u$ 到 $v$ 路径上的边，显然只会经过 $1$ 次，所以贡献为 $1$。 - 对于 $v$ 子树外并且不在 $u$ 到 $v$ 路径上的边，我们就可以选择经过/不经过，如果经过的话从上到下搜索再从下到上回溯会产生 $2$ 的贡献，综合两种情况这样的边的贡献仍然为 $1$。 所以 $(u,v)$ 对答案的贡献应该是 $n-sz_v$，而选中这个路径的概率为 $p_uq_v$（令 $p_i$ 为 $i$ 为起点的概率，$q_i$ 为 $i$ 为终点的概率），即答案应为： $$\sum\limits_u\sum\limits_vp_uq_v(n-sz_{u,v})$$ 不难看出 $sz_{u,v}$ 表示以 $u$ 为根时 $v$ 子树的大小。 现在我们考虑换根 dp，令 $cur=\sum\limits_vq_v(n-sz_v)$。 当根 $u\to u'$ 时： - $sz'_u\gets n-sz_u'

每次 ans\gets ans +cur\times p_u 换根即可。

P3600 随机数生成器

水题一道。

如果一个区间 [l,r]\subseteq[l',r']，那么 [l',r'] 这个区间对最大值没有影响，可以删去。于是剩下的 q 个区间将会互不包含。可以排序后用单调栈实现。

由期望公式 \mathbb E(ans)=\sum\limits_{i=1}^xi\times p_i，p_i 为 q 个询问的最大值为 i 的概率。

考虑变式，p_i 做一个前缀和变成 \sum\limits_{i=1}^{x}i\times (p_i-p_{i-1})，p_i 为最大值 \le i 的概率。

然后不难发现求最大值 \le i 的概率 p_i 即求最大值 \le i 的方案数 q_i ，因为这个方案数再除去 x^n 就是概率了。

最大值 \le i 代表每个区间的最小值都 \le i，即每个区间都至少有一个 \le i 的数。不妨枚举 n 个数中 \le i 的数的数量，那么 q_i=\sum\limits_{j=1}^{n}g_ji^j(x-i)^j，g_i 为在 1 到 n 里面塞 i 个数，使得每个区间都至少包含一个数的方案数。

然后就做完了，直接 dp：令 f_{i,j} 表示 1 到 i 选了 j 个点，第 i 个点必选，所有左端点 \le i 的区间都至少包含一个选的点的方案数。转移的时候考虑枚举上一个被选的点，如果能转移就说明这两个点之间没有区间。

可以预处理覆盖 i 点的最左区间 lp_i 和最右区间 rp_i，由于我们给区间排过序，所以转移的条件即 rp_k+1\ge lp_k。即 f_{i,j}=\sum\limits_{rp_k+1\ge lp_k}f_{k,j-1}。

不难发现 lp,rp 都有单调性，能够转移过来的 k 是一个区间，可以双指针维护左界，右界其实就是 i-1。可以前缀和优化求 f。

然后 g_i 就可以求了，枚举最后选的那个点：g_i=\sum\limits_{rp_j=q}f_{j,i}。

然后就随便做了。

P4707 重返现世

首先要知道一个叫 \text{Min-Max} 容斥的东西，然后我们要用它的加强版，即 拓展 \text{Min-Max} 容斥：

\min\limits_{k}(S)=\sum\limits_{T\subseteq S} \dbinom{|T|-1}{k-1}(-1)^{|T|-k}\max(T) \max\limits_{k}(S)=\sum\limits_{T\subseteq S} \dbinom{|T|-1}{k-1}(-1)^{|T|-k}\min(T)

上面所有的式子都是对期望成立的，即：

E(\min\limits_{k}(S))=\sum\limits_{T\subseteq S} \dbinom{|T|-1}{k-1}(-1)^{|T|-k}E(\max(T)) E(\max\limits_{k}(S))=\sum\limits_{T\subseteq S} \dbinom{|T|-1}{k-1}(-1)^{|T|-k}E(\min(T))

如果你没看懂的话，可以去隔壁博客。

介绍完前置知识就可以回到题目了。我们可以把题目看作每个原料有一个生成时间，即求第 n-k+1 大的期望值。为了简化式子，以下令 k\gets n-k+1，显然 k\le 11，并且求的是第 k 大的期望。

套用拓展 \text{Min-Max} 容斥，把前 k 大转换成最小：

E(\max\limits_{k}(S))=\sum\limits_{T\subseteq S} \dbinom{|T|-1}{k-1}(-1)^{|T|-k}E(\min(T))

显然对于每一种 T，可以把 T 中的原料看成一类，其它的看作另一类，那么抽到 T 中原料的概率显然就是 P_T=\dfrac{\sum\limits_{i\in T}p_i}{m}，由于E(\min(T)) 表示第一次抽到 T 中原料的期望时间，所以由简单期望知识我们知道 E(\min(T))=\dfrac{1}{P_T}=\dfrac{m}{\sum\limits_{i\in T}p_i}。

所以

\begin{aligned}ans_k&=\sum\limits_{T\subseteq S} \dbinom{|T|-1}{k-1}(-1)^{|T|-k}\dfrac{m}{\sum\limits_{i\in T}p_i}\\&=m\sum\limits_{T\subseteq S} \dfrac{\dbinom{|T|-1}{k-1}(-1)^{|T|-k}}{\sum\limits_{i\in T}p_i}\end{aligned}

然后考虑 dp，由于 k、m 都很小，于是可以纳入状态，令 dp_{i,j,k} 表示当前考虑前 i 种原料，\sum\limits_{i\in T}p_i=j 的时候 ans_k\times j 的值。

转移的话，其实非常显然。

\dbinom{|T|-1}{k-1}(-1)^{|T|-k}=\dbinom{|T|-2}{k-2}(-1)^{(|T|-2)-(k-2)}-\dbinom{|T|-2}{k-1}(-1)^{(|T|-2)-(k-1)}

于是这种情况可以从 dp_{i-1,j-p_i,k} 与 dp_{i-1,j-p_k,k-1} 转移过来。

总的转移式子就是：

dp_{i,j,k}=dp_{i-1,j,k}+dp_{i-1,j-p_i,k-1}-dp_{i-1,j-p_i,k} ### [CF1605F PalindORme](https://www.luogu.com.cn/problem/CF1605F) Difficulty : 2900 不知道是怎么想到的。ntf 实在是不平凡的。 你考虑如何判断一个序列是 $\text{good}$ 的。设重排后序列 $t_i$ 前缀 $[1,i]$ 和后缀 $[n-i+1,n]$ 按位或等于 $w_1$，$[1,i+1]$ 和 $[n-i,n]$ 按位或等于 $w_2$。不难发现 $w_1\subseteq w_2$，这说明 $w_2$ 和 $w_1$ 的**对称差**对应的那些位上，$t_{i+1}$ 和 $t_{n-i}$ 均为 $1$。于是扔掉顺序，就变成了 $b_i$ 里面任取两个数 $x,y$，令 $x',y'$ 为它们去掉当前按位或值 $V$ 是 $1$ 的位的值，那么 $x'=y'$，再将 $V\gets V\text{or}\ x'$。 合法的序列一定会判断合法，因为每步中满足条件的 $x,y$，如果它们没有被选，那么接下来选数时 $x,y$ 仍然合法。并且一定可以从一个不合法的序列中拆出一个合法的子序列，而且去掉这个子序列的或和为 $1$ 的位之后，剩下来的数**互不相同**。 为了避免算重，如果剩下的数中有 $0$，我们将其算进合法子序列内。 然后就可以数数了。设 $dp_{i,j}$ 为长度为 $i$，按位或的 $\text{popcount}$ 为 $j$ 的**不合法**序列的方案数。答案枚举 $j$ 求和即可。每次转移就枚举其合法子序列的长度以及值域（因为合法子序列的或值上的 $1$ 可以全部去除），显然： $$dp_{i,j}=\sum\limits_{p\in [0,i),q\in [0,j)}(g_{p,q}-dp_{p,q})\dbinom{i}{p}\dbinom{j}{q}2^{(i-p)q}f_{i-p,j-q}$$ 其中 $g_{i,j}$ 表示长度 $i$，值域 $[0,2^j)$ 的序列，按位或和为 $2^j-1$ 的序列个数。$f_{i,j}$ 表示长度 $i$，值域 $[1,2^j)$ 的序列，每个位置上的值**互不相同**，按位或和为 $2^j-1$ 的序列个数。$g_{p,q}-dp_{p,q}$ 就是合法子序列的个数，然后任取 $p$ 个位置和 $q$ 个二进制位。最后要求 $i-p$ 个数要**互不相同**，而且对于 $V$ 为 $1$ 的位，不合法的部分的数可以任选，所以乘上 $2^{(i-p)q}$。 至于如何计算 $f,g$，容斥一下，钦定一些位为 $1$，其余任选（$f$ 还是要满足非零且互不相同的条件）： $$f_{i,j}=\sum\limits_{k=0}^j\dbinom{j}{k}(-1)^{j-k}(2^k-1)^{\underline{i}}$$ $$g_{i,j}=\sum\limits_{k=0}^j\dbinom{j}{k}(-1)^{j-k}(2^k)^i$$ 做完了，复杂度 $O(n^2k^2)$。 ### [CF98E Help Shrek and Donkey](https://www.luogu.com.cn/problem/CF98E) Difficulty : 2700 显然，当双方均有牌的情况下，先手是不可能直接指定桌牌的：正确的概率为 $\frac{1}{m+1}$，错误的概率为 $\frac{m}{m+1}$，显然 $\frac{m}{m+1}\ge\frac{1}{m+1}$。 于是先手指定桌牌的情况只能是 $n=0$ 或 $m=0$： - $n=0$ 时，猜测没用（否则后手必胜），直接指定，正确的概率为 $\frac{1}{m+1}$。 - $m=0$ 时，先手直接指定自己没有的那张牌即可，概率为 $1$。 下面讨论 $n,m\neq 0$ 的情况。 考虑到先手进行猜测有两种情况：猜测自己有的牌、猜测自己没有的牌。称猜测自己有的牌为“诈骗”，猜测没有的为“询问”，分类讨论： 先手猜测的牌设为 $x$。 - 若先手诈骗： 后手可以选择**认为先手是询问**，此时后手没有 $x$ 并且认为先手没有 $x$，所以他认为桌牌是 $x$，于是这种情况下先手诈骗成功的概率为 $a=1$。 后手可以选择**认为先手是诈骗**，此时后手知道先手有 $x$，等价于先手摊牌 $x$，下一轮先后手交换，即 $b=1-f(m,n-1)$。 - 若先手询问： 那么先手有 $\frac{m}{m+1}$ 概率猜中对方的牌，有 $\frac{1}{m+1}$ 概率猜到桌牌。 无论后手选择先手是诈骗还是询问，如果猜中了对方的牌，对方都要摊牌，也就是两边的概率都有 $\frac{m}{m+1}\left(1-f(m-1,n)\right)$。 如果没猜中对方的牌（猜中了桌牌）。如果**后手认为先手在询问**，那么下一轮他就会直接指定桌牌，此时先手获胜概率为 $0$；如果**后手认为先手在诈骗**，后手下一轮就不会指定桌牌，而先手已经知道自己没有的 $x$ 后手也没有，会直接指定，此时先手概率为 $\frac{1}{m+1}$。 所以如果此时后手认为先手在询问，先手获胜概率为 $c=\frac{m}{m+1}(1-f(m-1,n))$；否则后手认为先手在诈骗，先手获胜概率为 $d=\frac{m}{m+1}(1-f(m-1,n))+\frac{1}{m+1}$。 --- 综合一下，发现先手只要选择了是诈骗还是询问，获胜概率全由**后手选择认为先手是诈骗还是询问**决定，设先手选择询问的概率为 $p$： - 后手认为先手询问，获胜概率 $p_1=(1-p)a+pc=(1-p)+\frac{mp}{m+1}(1-f(m-1,n))$。 - 后手认为先手诈骗，获胜概率 $p_2=(1-p)b+pd=(1-f(m,n-1))(1-p)+\frac{mp}{m+1}(1-f(m-1,n))+\frac{p}{m+1}$。 根据[纳什均衡策略](https://baike.baidu.com/item/%E7%BA%B3%E4%BB%80%E5%9D%87%E8%A1%A1/534868?fr=aladdin)，$p_1=p_2$，解得 $p=\frac{(m+1)f(m,n-1)}{(m+1)f(m,n-1)+1}$，于是我们递归求得 $p$ 再带入 $p1,p2$ 中任意一个就可以求出 $f(n,m)$ 了。 ### [AGC034F RNG and XOR](https://www.luogu.com.cn/problem/AT_agc034_f) 需要一点数学知识，因为这是集合幂级数优化 dp（？ 类似随机游走，令 $f_i$ 为第一次操作到 $i$ 的期望操作次数，$p_i$ 为每次操作数为 $i$ 个概率，显然有： $$f_i=\begin{cases}0&i=0\\1+\sum\limits_{j\;\text{xor}\; k\ =\ i}p_jf_k&i\neq 0\end{cases}$$ 显然可以高斯消元，不过是 $O(2^{3n})$ 的，寄飞。 考虑到转移过程中有类似异或卷积的东西，令 $(f*p)_i$ 为 $\sum\limits_{j\;\text{xor}\;k\ =i\ }f_jp_k$，那么 $i\neq 0$ 时，$(f*p)_i+1=f_i$。 考虑 $(f*p)_0$ 的值。由于 $\sum\limits_ip_i=1$，于是根据 FWT 的线性性： $$\begin{aligned}\sum\limits_i(f*p)_i&=\sum\limits_{i}f_i\\\sum\limits_{i\neq 0}(f*p)_i+(f*p)_0&=\sum\limits_{i\neq 0}f_i+f_0\\(f*p)_0&=f_0+2^n-1\end{aligned}$$ 由于 $f_0=0$，那么 $(f*p)_0=2^n-1$，所以用括号表示集合幂级数的话： $$(f_0\quad f_1\quad f_2\quad...\quad f_{2^n-1})*(p_0\quad p_1\quad p_2\quad ...\quad p_{2^n-1})=(f_0+2^n-1\quad f_1-1\quad f_2-1\quad ... \quad f_{2^n-1}-1)$$ 接下来就很套路了，由于卷积的每项都带有 $f_i$，那么给 $p_0$ 减去 $1$，相当于给每位减去了 $f_i$，因为 $i\;\text{xor}\;0\ =\ i$： $$(f_0\quad f_1\quad f_2\quad...\quad f_{2^n-1})*(p_0-1\quad p_1\quad p_2\quad ...\quad p_{2^n-1})=(2^n-1\quad -1\quad -1\quad ... \quad -1)$$ 这是 $F*P=F'$ 的形式，那么 $F=F'*P^{-1}$。后面两个都已知，FWT 后点值相除就好了……吗？ 注意到 $\text{FWT}(P)_0=\text{FWT}(F')_0=0$，$\text{FWT}(F)$ 第 $0$ 位你填个啥？ 注意到其他位都是对的，那一位可以看作一个变量，肯定有一个数填 $c$ 到这一位使得 IFWT 后是对的。那么我们直接对 $\left(0\quad \dfrac{\text{FWT(F')}_1}{\text{FWT(P)}_1}\quad \dfrac{\text{FWT(F')}_2}{\text{FWT(P)}_2}\quad ...\quad \dfrac{\text{FWT(F')}_{2^n-1}}{\text{FWT(P)}_{2^n-1}}\right)$ 做 IFWT，由于第 $0$ 位改变，影响的是每一项，而 IFWT 回去的结果是 $f'(0)$ 而不是 $f(0)=0$，所以给 $f'$ 整体减去 $f'(0)$ 所得就是答案了。 [ARC162F Montage](https://www.luogu.com.cn/problem/AT_arc162_f) Difficulty : 3190 手玩一下，容易转化题意为： > 按行从上到下填 $0/1$ 矩阵，设第 $i$ 个**非空**行上是 $1$ 的位置的集合为 $S_i$，满足： - 对于任意 $i>1$，令 $D=S_i\cup S_{i-1}$。 - 若 $D=\varnothing$，则 $S_i$ 中所有元素均比 $S_{i-1}$ 中任意元素小，即 $\max\limits_{i\in S_i}i<\min\limits_{i\in S_{i-1}}i$。 - 若 $D\neq\varnothing$，则 $S_i,S_{i-1},D$ 从小到大排序后，$D$ 为 $S_i$ 的后缀，为 $S_{i-1}$ 的前缀，即 $\max\limits_{i\in S_i\setminus D}i<\min\limits_{i\in D}i\le \max\limits_{i\in D}i<\min\limits_{i\in S_{i-1}\setminus D}i$。 现在这个限制是从右上角走到左下角，那不如先把行翻转一下，就变成了从左上角到右下角： - $D=\varnothing$，$\min\limits_{i\in S_i}i>\max\limits_{i\in S_{i-1}}i$。 - $D\neq\varnothing$，$\min\limits_{i\in S_i\setminus D}i>\max\limits_{i\in D}i\ge \min\limits_{i\in D}i>\max\limits_{i\in S_{i-1}\setminus D}i$。 那我们直接把空行删掉，令 $f_{i,j,k}$ 表示考虑到第 $i$ 行，第 $i$ 行一共有 $j$ 个 $1$，最右边的 $1$ 的位置为 $k$ 的方案数。转移枚举新的最右边的 $1$ 的位置 $p$，$D$ 的大小 $s$，$S_{i+1}\setminus D$ 的大小 $l$，转移系数就是个组合数： $$f_{i,j,k}\dbinom{p-k-1}{s-1}\to f_{i+1,l+s,p}$$ 枚举非空的行数，答案就是： $$\text{ans}=1+\sum\limits_{i=1}^{n}\dbinom{n}{i}\sum\limits_{j=1}^m\sum\limits_{k=1}^{m-j+1}f_{i,j,k}$$ 直接做是 $O(n^6)$ 的。利用不同的 $l$ 转移相同可用前缀和优化至 $O(n^5)$。 然后我们发现把矩阵转置一下，将 $n,m$ 交换不影响答案，也就是说我们可以把空的列也拿出来。于是每个 $S_i$ 就是一段区间了，且 $S_i,S_{i+1}$ 要么相交不包含要么相邻，$S_{i+1}$ 在 $S_i$ 的右边。 将 $f_{i,j,k}$ 重新定义为 $S_1=[1,r_1],S_i=[j-k+1,j]$，满足以上限制的方案数。其实就是把前面的 $j,k$ 两维交换了一下。 那么答案变为： $$\text{ans}=1+\sum\limits_{i=1}^n\sum\limits_{j=1}^m\dbinom{n}{i}\dbinom{m}{j}\sum\limits_{k=1}^jf_{i,j,k}$$ 转移还是枚举 $S_{i+1}$ 的两个端点 $p,q$，满足 $j-k+1\le p\le j+1,\max(p,j)\le q\le m$: $$f_{i,j,k}\to f_{i+1,q,q-p+1}$$ 然而这还是 $O(n^5)$ 的。由于对于不同的 $p$ 贡献相同，设 $f'_{i,j,k}$ 为第三维差分后的 $f$ 数组，可用前缀和优化至 $O(n^4)$： $$f_{i,j,k}\to f'_{i+1,q,q-\min(j+1,q)+1},-f_{i,j,k}\to f'_{i+1,q,q-j+k+1}$$ 单独将 $q=j$ 的转移拎出来，这部分 $O(n^3)$： $$f_{i,j,k}\to f'_{i+1,j,1},-f_{i,j,k}\to f'_{i+1,j,k+1}$$ 剩下的是 $q\ge j+1$ 的转移： $$f_{i,j,k}\to f'_{i+1,q,q-j},-f_{i,j,k}\to f'_{i+1,q,q-j+k+1}$$ 这还是 $O(n^4)$ 的，但是我们观察到第二维和第三维的差为定值且与 $q$ 无关，所以令 $g_{i,j,k+1}=f'_{i,j,j-k}$： $$f_{i,j,k}\to g_{i+1,q,j+1},-f_{i,j,k}\to g_{i+1,q,j-k}$$ 注意到 $q\in [j+1,m]$，再对 $g$ 的第二维进行差分记作 $g'$，前缀和优化即可做到 $O(n^3)$： $$f_{i,j,k}\to g'_{i+1,j+1,j+1},-f_{i,j,k}\to g'_{i+1,j+1,j-k}$$ 最终时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。 ### [NOMURA Programming Competition 2020 D Urban Planning](https://www.luogu.com.cn/problem/AT_nomura2020_d) Difficulty : 2810 考虑排列 $P_i$ 已经固定了的情况，那么连边 $i\to P_i$ 形成有向图 $G$，最小连边数就是 $N$ 减去弱连通块数。善良的出题人已经告诉你连边方案就是 $(N-1)^K$，所以答案就是 $N(N-1)^K$ 减去所有连边方案中弱连通块数量总和。于是只需要考虑所有连边方案中弱连通块数量总和即可。 注意到最后这张图一定是个**内向基环树**森林，所以某些 $P_i$ 未确定时就应该是个**内向基环树**加若干**内向树**构成的森林（孤立点也算内向树）。考虑一个弱连通块 $G'\subseteq G$，按照其形态分类： - $G'$ 为**内向基环树**，则 $G'$ 内的点的 $P_i$ 均固定，且只有一个环，所以对一个连边方案的贡献为 $1$，算上外部连边方案，总贡献为 $(N-1)^K$。 - $G'$ 为**内向树**，则 $G'$ 内存在**唯一** $P_i$ 不固定的点 $i$，就是内向树的**根**。这个连通块有两种选择： - $P_i$ 选择 $G'$ 内的点，那么 $P_i$ 有 $|V_{G'}|-1$ 种选择方案（不能选自己），外部还剩 $(N-1)^{K-1}$ 种方案，那么贡献为 $(|V_{G'}|-1)(N-1)^{K-1}$。 - $P_i$ 选择 $G'$ 外的点，那么 $G'$ 就变成了某个大内向基环树的子图，而这个基环树除去环边是由若干个内向树组成的。这类贡献有关其它连通块大小，单独拉出来在下面讨论。 刚才的问题可以转化为单独考虑每个大环的贡献，大环是由从 $G$ 中选出若干个**形态为内向树的连通块**，选出它们的根之后连接组成的。假设选择了 $G_1,G_2,\cdots,G_m$ $m$ 个连通块形成一个环，环上的树的排列方式有圆排列 $(m-1)!$ 种，每个根 $i$ 的 $P_i$ 可以在下一棵内向树的点中任意选择，选择方案有 $\prod |V_{G_i}|$ 种（$V_G$ 为构成子图 $G$ 的点集），其余 $P_i$ 未匹配的 $i$ 有 $K-m$ 个，选出这些 $P_i$ 有 $(N-1)^{K-m}$ 种方案。 那么设组成基环树的内向树数量为 $m(m\ge 2)$，方案数就是： $$(m-1)!(N-1)^{K-m}\sum\limits_{G_1,G_2,\cdots,G_m}\prod\limits_{i=1}^m|V_{G_i}|$$ 后面这个东西就是个背包，设 $f(m)=[x^m]\prod\limits(|V_{G_i}|x+1)$，可以 $O(N^2)$ 背包 dp 求出来，那么 $m$ 的总贡献就是： $$(m-1)!(N-1)^{K-m}f(m)$$ 然后算上之前的贡献就做完了，复杂度 $O(N^2)$。瓶颈在于计算 $f(m)$，可以多项式优化。 ## 数位 dp 实在没做过啥数位 dp 的题…… ### [CF750G New Year and Binary Tree Paths](https://www.luogu.com.cn/problem/CF750G) Difficulty : 3200 考虑枚举路径的 LCA 为 $x$。 如果是一条直链，设其长度（点数）为 $l$，那么一直往左子树走的话，总和就是： $$x+2x+4x+\cdots +2^{l-1}x=(2^l-1)x\le s$$ 由于 $l$ 是 $O(\log s)$ 的，考虑枚举 $l$，反解出 $x$： $$x\le \left\lfloor\frac{s}{2^l-1}\right\rfloor$$ 不难发现这同样是 $x$ 的下界。具体地，令 $x'=x-1$，考虑从 $x'$ 一直往右子树走的路径，此时路径和取到最大，只需证明这个最大值小于 $x$ 为开头的链的最小值（一直往左走）即可： $$\begin{aligned}x'+(2x'+1)+(2(2x'+1)+1)+\cdots&=(2^l-1)x'+2^l-l-1\\&=(2^l-1)x-l< (2^l-1)x\end{aligned}$$ 所以此时的 $x$ 是固定的。所以枚举 $l$，算出 $x$ 后自顶向下调整（将某层的左儿子翻转到右儿子）判断是否能取到 $s$ 即可。 类似直链的情况，拓展到分叉上：枚举以左儿子为开头向下的链长度（点数）为 $l_1$，右儿子为 $l_2$。这条路径的总和为： $$\begin{aligned}f(x,l_1,l_2)&=x+(2^{l_1}-1)2x+(2^{l_2}-1)(2x+1)\\&=(2^{l_1+1}+2^{l_2+1}-3)x+2^{l_2}-1\le s\end{aligned}$$ $$x\le \left\lfloor\frac{s-2^{l_2}+1}{2^{l_1+1}+2^{l_2+1}-3}\right\rfloor$$ 同样可以发现这里的 $x$ 是固定的，解出 $x$ 后令 $r=s-f(x)$。考虑翻转链上一个左儿子产生的贡献，等价于下列问题： > 给定 $2$ 个集合 $\{2^{1}-1,2^{2}-1,\cdots ,2^{l_1}-1\}$ 和 $\{2^{1}-1,2^{2}-1,\cdots ,2^{l_2}-1\}$，从中选择若干元素，使得总和为 $r$，求方案数。 这东西显然很不好做，考虑转成 $2$ 的幂，枚举选出来元素的个数 $n$，相当于从 $\{2^1,2^2,\cdots, 2^{l_1}\}\cup\{2^1,2^2,\cdots, 2^{l_2}\}$ 中选择 $n$ 个元素，和为 $r+n$。这里的集合为可重集。 显然 $2\nmid (r+n)$ 时无解，否则整体除 $2$ 后数位 dp。令 $f_{i,j,0/1}$ 表示从小到大考虑到 $t=\frac{r+n}{2}$ 的第 $i$ 位，选了 $j$ 个数，当前位是否有进位的方案数。答案就是 $f_{\log t,n,0}$，转移的话考虑两边同时取/取一个/都不取分类讨论一下即可。 复杂度 $O(\log^5 s)$。 ## dp 套 dp ### [SDOI2022 小 N 的独立集](https://www.luogu.com.cn/problem/P8352) dp 套 dp 的含义就是用外层 dp 的**状态**表示内层 dp 的**结果**。 考虑普通的树形 dp 求最大权独立集，$f_{u,0/1}$ 表示 $u$ 的子树中 $u$ 是否选择的最大权独立集大小，转移显然。 那么一个朴素的想法就是令 $g_{u,x,y}$ 表示 $f_{u,0}=x$，$f_{u,1}=y$ 的方案数。每次枚举并加入儿子 $v$ 的贡献： $$g'_{u,x+\max(z,w),y+z}\gets g _{u,x,y}\cdot g_{v,z,w}$$ 然而这样状态数是 $O(n^3k^2)$ 的，根据树形背包知道这个做法是 $O(n^4k^4)$ 的。考虑优化。 考虑修改状态，令 $f_{u,0/1}$ 为 $u$ 子树是否强制不选择 $u$ 的最大权独立集大小。转移是显然的。 注意到 $0\le f_{u,0}-f_{u,1}\le a_u\le k$，分类讨论即可。 那么可以设 $g_{u,x,y}$ 表示 $f_{u,1}$ 为 $x$，$f_{u,0}-f_{u,1}$ 为 $y$ 的方案数，显然有状态数 $O(n^2k^2)$，再做树形背包就是 $O(n^2k^4)$ 的了。转移推一下即可。 ## 数据结构优化 ### [CF115E Linear Kingdom Races](https://www.luogu.com.cn/problem/CF115E) Difficulty : 2400 令 $f_i$ 表示考虑前 $i$ 条道路的最大收益。 如果不修复这条道路，$f_i=f_{i-1}$。 如果修复，$f_i=\max\limits_{0\le j<i}\{f_j-c(j+1,i)+p(j+1,i)\}$，即将 $[j+1,i]$ 全部覆盖。 然后这个 $dp$ 大概是 $O(n^2)$ 的，用脑子线段树在线维护跑到某个 $i$ 时每个 $j$ 的 $f_j-c(j+1,i)+p(j+1,i)$ 即可 $O(n\log n)$。 ### [ZJOI2010 基站选址](https://www.luogu.com.cn/problem/P2605) 常规套路，设 $dp_{i,j}$ 表示在第 $i$ 个村庄建立第 $j$ 个基站，不考虑 $i+1$ 到 $n$ 对答案贡献的最小费用。转移显然有： $$dp_{i,j}=\min\limits_{1\le k\le i-1}\{dp_{k,j-1}+cost_{k,i}\}+c_i$$ 其中 $cost_{k,i}$ 表示如果**在 $i$ 和 $j$ 两个位置建站**，它们之间村庄需要的总补偿。为了方便，我们从 $1$ 到 $i-1$ 枚举 $k$，并把 $dp_{i,j}(i<j)$ 的值赋为 $\inf$。 暴力做是 $O(n^2k)$ 的，考虑用数据结构优化。 这个状态的第二维肯定不能扔，考虑在最外层枚举 $j$，那么状态转移变为： $$dp_i=\min\limits_{1\le k < i}\{dp_k+cost_{k,i}\}+c_i$$ 我们想用线段树**动态维护对于每一个 $k$，$dp_k+cost_{k,i}$ 的值**，那么转移就变成了区间取 $\min$。 当 $i-1$ 向 $i$ 移动时，有一些 $cost_{k,i}$ 会增加，我们考虑统计它们。我们考虑对所有的 $i$，计算出在 $k$ 点建站使其被覆盖的最大和最小的 $k$，记为 $l_i,r_i$，并在 $i$ 移动时，考虑计算每个 $r_j=i-1$ 的 $k$ 对 $cost$ 的贡献，显然对于一个 $r_j=i-1$ 的 $j$，它会使得 $cost_{1,i}$ 到 $cost_{l_j-1,i}$ 上的值全部加上 $w_j$。因为在这个区间内建站都不会覆盖到它，并且 $i$ 也不会覆盖到它。 于是我们的线段树只需要维护区间加法，区间取最小值即可。复杂度 $O(kn\log n)$。 ### [CF1175G Yet Another Partiton Problem](https://www.luogu.com.cn/problem/CF1175G) Difficulty : 3000 应该是一个很通用的解法。 一个显然的分段 dp： > $f_{j,i}$ 表示前 $i$ 个数分 $j$ 段的方案数，$f_{j,i}\gets \min\limits_{k=0}^{i -1}f_{j-1,k}+w(k+1,i)$。 可以滚动数组，$f_{i}\gets \min\limits_{k=0}^{i -1}g_{k}+w(k+1,i)$。这是好理解的。 考虑到分段 dp 的价值函数大多数满足决策单调性，然后就发现 $w(k+1,i)=(i-k)\cdot\max\limits_{r=k+1}^ia_r$ 不满足决策单调性，很好，寄。 考虑 $[1,i]$ 这个前缀中每个下标 $j$，求出 $v_j=\min\limits_{k=j+1}^ia_k$，那么 $v$ 显然能够分成若干个连续段，每段 $v$ 值相等。并且 $i\to i+1$ 时，这个连续段是好维护的，使用单调栈即可。注意到这个维护顺序和 dp 顺序一样，这也非常好。 考虑一个连续段 $d=v_l=v_{l+1}=v_{l+2}=\cdots =v_r$，对于 $j\in [l,r]$，$w(j+1,i)=(i-j)\cdot d$，所以对于这个段我们只需要找到 $\min\limits_{l\le j\le r}g_j+d\cdot(i-j)=\min\limits_{l\le j\le r}g_j+d\cdot i-d\cdot j=d\cdot i+\min\limits_{l\le j\le r}g_j-d\cdot j$。于是对点集 $\{(j,g_j)\mid j\in [l,r]\}$ 维护一个**下凸壳**，每次拿斜率为 $d$ 的直线切这个凸包即可，我们给连续段标号（实际实现可以直接用右端点编号），并求出第 $l$ 个连续段的切点为 $(p_l,g_{p_l})$。 那么我们需要对于所有连续段 $l$，求出 $\min\limits_{l}g_{p_l}+(i-l)\cdot v_{p_l}$，我去，这太典了，这是个关于 $i$ 的一次函数，直接用**李超线段树**维护即可。具体来说，当 $i\to i+1$ 时，可能会合并一些连续段，假如合并的是 $x,y$ 连续段，那么我们将 $x,y$ 里面两个下凸壳合并起来（注意使用**启发式合并**），取最优的 $(p_l,g_{p_l})$ 决策点，将 $y=g_{p_l}-l\cdot v_{p_l}+v_{p_l}\cdot i$ 加入李超线段树，并删去原本 $x,y$ 两个下凸壳里面的决策点。 由于要实现删除，所以要用可持久化李超树/可撤销李超线段树。可持久化的话，每个连续段标号为右端点下标，直接从单调栈的栈顶（往前找第一个大于 $a_i$ 的位置）的版本继承过来就可以了。 复杂度 $O(kn\log n)$。 ### [CF1530H Turing's Award](https://www.luogu.com.cn/problem/CF1530H) Difficulty : 3400 你发现这个覆盖不太好考虑，考虑时间倒流，变成如下形式： > 一开始，小 A 的位置上有一个数 $a_n$，然后对于接下来 $n-1$ 步，每次小 A 可以向左走/向右走/不动，然后如果此时小 A 所站的位置上**没有数**，就写上 $a_i$，求最后形成序列的最长上升子序列长度。 考虑到任意时刻的序列一定是包含原点的连续序列 $b$，并且此时不能覆盖有数的位置，那么 $a_i$ 只可能插入到 $b$ 的首尾两个位置。 我们将所有**最终**在 $b$ 中的元素 $a_i$ 成为「好」的元素，显然 $a_n$ 一定是好元素，观察到： 1. 我们并不关心小 A 走到 $b$ 中间哪个**位置**，只关心他是否有**时间**在已经确定的连续好元素之间移动。例如，目前考虑了 $a_i,a_{i+1},\cdots, a_{n}$，钦定 $a_i$ 为好元素并且插入到 $b$ 的**首位**（插入末尾的情况是对称的），目前 $a_i,a_{i+1},\cdots ,a_n$ 中一共有 $k$ 个好元素，考虑第 $k+1$ 个好元素 $a_j(j<i)$： - 如果 $a_j$ 插入在 $b$ 的**首位**，我们可以在小 A 走过 $i-1,i-2,\cdots,j+1$ 的时候都选择留在原位，这样保证不会覆盖，然后 $j$ 时刻再向左移动一位。所以这种情况没有限制。 - 如果 $a_j$ 插入在 $b$ 的**末尾**，小 A 要走过 $k$ 个好元素。那么需要满足 $i-j\ge k$。 2. 考虑一个好元素 $a_j$（$j\neq n$）如果存在一种方案使得 $a_j$ 在最终的 $b$ 序列里不在 LIS 中，一定存在一种方案使得 $a_j$ 最终不在 $b$ 序列中，因为可以在时刻 $j$ 留在原地不动。所以我们更改好元素的定义：最终出现在 **LIS** 中的元素（包括 $a_n$）。 然后我们可以讨论 $a_n$ 是否属于 LIS，考虑 dp： 令 $f_L(k,i)$ 表示当前从 $n$ 考虑到 $i$，$a_i$ 插入到了 LIS 的**首位**，目前一共有 $k$ 个好元素，LIS **末尾**元素的**最小值**；$f_R(k,i)$ 表示当前从 $n$ 考虑到 $i$，$a_i$ 插入到了 LIS 的**末尾**，目前一共有 $k$ 个好元素，LIS **首位**元素的**最大值**。那么我们要求的就是最大的 $k$，使得存在一个 $i$，状态 $f_{L}(k,i)$ 或者 $f_{R}(k,i)$ 合法（属于 $[1,n]$）。 根据 $a_n$ 是否属于 LIS，我们可以确定 dp 的初始状态。 考虑 $f_{L}(k,i)$ 可以贡献到的状态（$f_R(k,i)$ 类似），讨论新的好元素 $a_j$ 放左还是放右即可： - $f_{L}(k,i)\to f_{L}(k+1,j)\quad j<i\land a_j<a_i

那么不难得到 f_{L}(k,i),f_{R}(k,i) 的转移：

\begin{aligned}f_{L}(k+1,i)=\min\left(\min\limits_{j>i\land a_j>a_i}f_{L}(k,j),\min\limits_{j\ge i+k\land f_R(k,j)\ge a_i}a_j\right)\\f_{R}(k+1,i)=\max\left(\max\limits_{j>i\land a_j<a_i}f_{R}(k,j),\max\limits_{j\ge i+k\land f_L(k,j)\le a_i}a_j\right)\end{aligned}

显然可以优化，用两个数据结构支持查询前缀 \max 和后缀 \min 即可。复杂度 O(kn\log n)，k 为答案，考虑到均匀随机序列的 LIS 长度期望为 O(\sqrt n)，k 取 O(\sqrt n)，复杂度 O(n\sqrt n\log n)。

其实这里有一个简易的 dp 优化套路：将 dp 答案与状态的一维交换，例如我们也可以按照 LIS 的首尾位为状态 dp，但是复杂度更劣。所以把 LIS 长度列入 dp 状态。

斜率 | 单调队列 | 决策单调性 | 凸完全单调性优化

CF311B Cats Transport

Difficulty : 2400

对于每只猫，算出**最晚的能够 pick 它的出发时间 $t_i$**，这个可以用前缀和做。 然后我们将 $t$ 序列从小到大排序，我们发现一个人 pick 到的猫在这个序列上一定是一段连续的区间。 然后问题就转换成了给定一个序列 $t$，将其分成 $p$ 段，使得 $\sum\limits_k\sum\limits_{i=l_k}^{r_k}t_{r_k}-t_i$ 最小。 令 $f_{i,j}$ 表示分成 $i$ 段，末尾为 $j$ 的最小答案。设 $s_i=\sum\limits_{k=1}^{i}t_k$，则不难得出转移： $$f_{i,j}=\min\limits_{k=0}^{j-1}(f_{i-1,k}+t_j(j-k)-s_j+s_k)$$ 于是第 $i-1$ 行的 $f$ 值会影响到第 $i$ 行的值，考虑开 $p$ 个单调队列来优化 dp。 **为了题解简洁，以下把第一位省略。** 转移的式子为 $f_i=-t_ij+s_j+f_j-s_i+it_i$。 整理一下：$f_i+s_i-it_i=-t_i\times j+(s_j+f_j)

然后这就是标准的斜率优化形式了，复杂度 O(mp)。

CF868F Yet Another Minimization Problem & CF1527E Partition Game

Difficulty : 2500

记两道决策单调性优化 dp 板子。

对于前一道，dp_{i,j} 表示前 j 个数分 i 段的最小答案，dp_{i,j}\gets dp_{i-1.k}+w(k+1,j)。

首先显然这个满足决策单调性，然后就可以分治 dp 了。

第二道差不多一样，移动指针麻烦一点。

CF321E Ciel and Gondolas

决策单调性的另一个结论。

记 w(l,r) 为 [l,r] 之间的两两和，f_{i,j}\gets\min\limits_{k=1}^j\{f_{i-1,k-1}+w(k,j)\}。

显然的决策单调性，分治可以做到 O(nk\log n)，除去 O(n\log n\log k) 的 wqs 二分不谈，其实可以 O(n^2)。

一个满足四边形不等式的状态，记录 op(i,j) 为 (i,j) 的最优决策点。则：

op(l,r-1)\le op(l,r)\le op(l+1,r)

然后记录每个状态的转移区间，直接 dp 即可。

正确性及复杂度证明可见 OI Wiki。

CF1699E Three Days Grace

Difficulty : 2600

不知道算不算双指针优化。

考虑最终答案方案的值域。

如果固定值域左端点为 i，此时最小答案应是 \max\{f_{a_k}\}-i，f_k 表示将 k 拆分成若干个不小于 i 的数后得到的最大因数的最小值。

于是考虑在 i 从 m 到 1 的过程中，转移 f_k。

首先如果 i\nmid k，显然 f'_k=f_k（f' 表示从 i+1 转移 i 后的 f 数组）。

如果 i\mid k，考虑拆出一个 i 的条件是 \frac{k}{i}\ge i，即 k\ge i^2 时，f'_{k}\gets f_{\frac{k}{i}}。

注意到被转移的都是 i 的倍数，于是如果枚举每次转移的位置，就可以做到调和级数转移了。

还有一个问题，如何统计答案。也就是对于每一个 i，求出 \max\{f_{a_k}\}。

我们发现转移时是取 \min 的，也就是说 f 的最大值单调不增。

用另外一个指针 j，表示 \max\{f_{a_k}\} 即可。由于 j 随着 i 的下降而不增，移动 j 的复杂度是 O(m) 的。

总复杂度 O(m\log m)。

CF1603D Artistic Partition

Difficulty : 3000

首先如果 2^k>n，答案为 n。

否则 k\le \log_2n，然后就可以令 dp_{i,j} 表示前 i 个数分 j 段的最小答案。

考虑到： $$\begin{aligned}c(l,r)=&\sum\limits_{i=l}^{r}\sum\limits_{j=l}^{r}[\gcd(i,j)\ge l]\\=&\sum\limits_{k=l}^{r}\sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}[\gcd(i,j)=k]\\=&\sum\limits_{k=l}^{r}\sum\limits_{i=1}^{r/k}\varphi(i)\\=&\sum\limits_{k=l}^{r}S_{\varphi}(\left\lfloor\frac{r}{k}\right\rfloor)\end{aligned}$$ 我们发现它有决策单调性！ 于是可以 $O(n\sqrt n)$ 预处理 $val_{i,j}$ 表示 $r=i$ 并且 $\left\lfloor\frac{n}{k}\right\rfloor=j$ 时 $\sum\limits_{k=l}^{r}S_{\varphi}(\left\lfloor\frac{r}{k}\right\rfloor)$ 的值（此时 $l$ 为满足 $\left\lfloor\frac{n}{l}\right\rfloor=\left\lfloor\frac{n}{r}\right\rfloor$ 最小的 $l$）。 然后 $c(l,r)=\sum\limits_{k=1}^{r/l-1}val_{r,i}+S_{\varphi}(\left\lfloor\frac{r}{l}\right\rfloor)(r'-l+1)$，$r'$ 为使 $\left\lfloor\frac{r}{r'}\right\rfloor=\left\lfloor\frac{r}{l}\right\rfloor$ 最大的 $r$，可以 $O(1)$ 求出。 于是可以在 $O(n\sqrt n+n\log^2 n)$ 的复杂度内解决此题。 但我觉得预处理太麻烦了咋办？ 我们发现，在移动区间左端点时，每向左移 $1$ 位就对转移答案贡献 $S_{\varphi}(\left\lfloor\frac{r}{l}\right\rfloor)$，而总移动次数不超过 $O(n\log n)$ 次，我们可以在开始就暴力 $O(\sqrt n)$ 算出 $c(pr+1,mid)$ 的值，然后 $l$ 指针从 $pr$ 移到 $pl$（可转移的区间）的过程中加贡献即可。 由于对于每个 $mid$ 仅算了一次 $c(pr+1,mid)$，于是这部分应该是 $O(n\sqrt n\log n)$ 的，整个 $dp$ 过程应该是 $O(n\sqrt n\log n+n\log^2 n)$ 的，但是不知道为啥能过（可能是因为每次计算 $c(pr+1,mid)$ 区间长度远远达不到 $n$），如果有会证明时间复杂度的好哥哥可以打我（ ### [ARC125F Tree Degree Subset Sum](https://www.luogu.com.cn/problem/AT_arc125_f) Difficulty : 3500 pb 讲课题。 显然树的具体形态对题目影响不大，那么我们知道 $\sum\limits_{i=1}^nd_i=2n-2$ 即可扔掉树的条件。即： > 给定 $n$ 个 $d_i$，和为 $2n-2$，求 $(x,y)$ 满足 $0\le x\le n$ 且 $\exists S\subseteq \{1,2,\cdots n\},|S|=x,\sum\limits_{i\in S}d_i=y$ 的数量。 我们考虑如何解决这个问题。首先可以将所有 $d_i$ 减去 $1$，那么 $\sum\limits_{i=1}^nd_i=n-2$。然后我们考虑证明，对于任意的 $y$，设 $m(y)$ 和 $M(y)$ 为**最小和最大的 $x$** 使得 $(x,y)$ 合法，那么有 $\forall i\in [m(y),M(y)]$，$(i,y)$ 合法： > - 设 $x(S)=|S|,y(S)=\sum\limits_{i\in S}d_i$。 > - 我们设 $d_i=0$ 的 $i$ 的个数为 $z$，由于 $m(y)$ 的方案中没有选 $d_i=0$ ，$M(y)$ 的方案中一定选了 $z$ 个 $d_i=0$，所以只需要证明 $M(y)-m(y)\le 2z+1$ 即可通过调整 $0$ 的个数构造出 $x\in [m(y),M(y)]$。 > - 由于对于每个集合 $S\in \{1,2,\cdots n\}$，$-z\le y(S)-x(S)\le z-2$（左边全取 $0$，右边全取非 $0$），所以对于任意的 $y$，$-z\le y-M(y)\le y-m(y)\le z-2$。 > - 解不等式即可得到 $M(y)-m(y)\le 2z-2 < 2z+1$。 考虑得到了 $\forall i\in [m(y),M(y)]$，$(i,y)$ 合法这个结论，如何求出方案数。由于 $y\le n-2$，考虑处理出对于每个 $y$，$M(y)$ 和 $m(y)$ 的值，然后对 $M(y)-m(y)+1$ 求和就是答案。 注意到 $d$ 的总和为 $n-2$，显然 **$d_i$ 中非 $0$ 的互不相同的数**至多只有 $O(\sqrt n)$ 个，不难想到用**单调队列优化多重背包**。具体地，以 $M(y)$ 为例，设 $c_i=\sum\limits_{j=1}^n[d_j=i]$，$f_{i,j}$ 表示考虑了 $1$ 到 $i$ 中的所有 $d_k=i$，当前 $y(S)$ 为 $j$ 的方案数。那么： $$f_{i,j}\gets \max\limits_{k=0}^{c_i}(f_{i-1,j-ki}+k)$$ 套路地将 $j$ 拆成 $xi+y$，且 $0\le y<i$，设 $g_{y,x}=f_{i,xi+y}$，$g'_{y,x}=f_{i-1,xi+y}$： $$\begin{aligned}g_{y,x}&=\max\limits_{k=0}^{c_i}(g'_{y,x-k}+k)\\&=\max\limits_{k=0}^{c_i}(g'_{y,x-k}-(x-k))+x\end{aligned}$$ 这就是经典的单调队列优化的形式了。考虑外层枚举 $y\le i$，内层 $x\le \left\lfloor\dfrac{n}{i}\right\rfloor$，物品数量为 $O(\sqrt n)$，总复杂度是 $n\sqrt n$ 的。 最后统计答案需要将 $d_i=0$ 的贡献算上。 ### [Luogu8544 「Wdoi-2」禁断之门对面，是此世还是彼世](https://www.luogu.com.cn/problem/P8544) #### Part 1. 转换 由于 $A_{i,j}=a_ib_j$，这个 $f(B)$ 显然可以化简： $$\begin{aligned}f(B)&=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^t\sum\limits_{k=\min(B_{i,j},B_{i+1,j})}^{\max(B_{i,j},B_{i+1,j})}A_{i,k}\\&=\sum\limits_{i=1}^n\sum\limits_{j=1}^t\sum\limits_{k=\min(B_{i,j},B_{i+1,j})}^{\max(B_{i,j},B_{i+1,j})}a_ib_k\\&=\sum\limits_{i=1}^na_i\sum\limits_{j=1}^tS_{\max(B_{i,j},B_{i+1,j})}-S_{\min(B_{i,j},B_{i+1,j})-1}\end{aligned}$$ $S_i$ 为 $b$ 数组的前缀和。 发现若得到 $g(B_1,B_2)=\sum\limits_{j=1}^tS_{\max(B_{1,j},B_{2,j})}-S_{\min(B_{1,j},B_{2,j})-1}$ 的最小值，我们可以令 $B_{2k+1}=B_1,B_{2k+2}=B_2$。这样显然最优。也就是说，$f(B)=\left(\sum\limits_{i=1}^na_i\right)\cdot \min g(B_1,B_2)$。 问题转换为找到一个 $B_1,B_2$，分别满足每个元素两两不同，都在 $[1,m]$ 之间，并且对应的位置上的元素不同，使得 $g(B_1,B_2)$ 最小。 由于同一行元素两两不同以及值域的限制，考虑转换成匹配问题。相当于现在有两列数（分为左部和右部），分别为 $1,2,\cdots ,m$，在左部中选择 $t$ 个数，并和右部的 $t$ 个数匹配。满足不存在形如 $(i,i)$ 的匹配，一对匹配 $(i,j)$ 的价值就是 $S_{\max(i,j)}-S_{\min(i,j)-1}$，也就是 $b_{\min(i,j)}+b_{\min(i,j)+1}+\cdots+b_{\max(i,j)}$。一组匹配的价值就是每对匹配的价值之和，求**钦定有 $t$ 对匹配的最小匹配**。 #### Part 2. 猜想 有个比较感性的想法，就是**一对匹配不应该跨过太大的距离**。考虑从左到右按顺序匹配，如果匹配跨过了一段空区间，那么不如不跨过这段区间，因为这样减小了代价的同时也给后面的点更多的选择方案。 另一个比较感性的想法，**匹配应该尽可能不交叉**。这里借用[这篇题解](https://www.luogu.com.cn/blog/McHf/solution-Wdoi2-1E)的图： ![](https://cdn.luogu.com.cn/upload/image_hosting/j58zojf0.png) 如上图，匹配 $(2,5)(4,3)$ 显然不如匹配 $(2,3),(4,5)$。即如果存在交叉的匹配，我们尝试交换匹配以减少价值。而且可以发现减少交叉必定不劣。 手玩一些数据之后，我们发现最优解中，$i$ 只能形成 $(i,j)(j\in \{i-2,i-1,i+1,i+2\})$ 的匹配。我们下面试图证明这个结论。 #### Part 3. 证明 $i$ 显然可以和 $i-1,i+1$ 匹配，即证最优解中合法匹配 $(i,j)$ 满足 $j-i\le 2$。下面**从左到右**考虑一组匹配 $(i,j)(j>i+2)$ 如何调整（小于 $i$ 的左部点的匹配均满足猜想），$j<i-2$ 根据对称性同理： - 若 $\exists k\in \{1,2\}$，不存在匹配 $(?,i+k)$（即右部的 $i+k$ 没有被匹配），显然将 $(i,j)$ 调整为 $(i,i+k)$ 更优。 - 否则存在 $(x,i+1),(y,i+2)$ 的匹配，且我们从左到右调整，显然有 $x,y>i$ 且 $x\neq y$。注意到匹配 $(i,j)$ 和 $(x,i+1),(y,i+2)$ 都有上述的**交叉**，所以我们试图交换两个匹配的右部点以减少交叉：若 $x=j$，则 $y\neq j$，将原匹配 $(i,j)(y,i+2)$ 重组为 $(i,i+2)(y,j)$ 即可；若 $x\neq j$，将原匹配 $(i,j)(x,i+1)$ 重组为 $(i,i+1)(x,j)$ 即可。 这样我们就能够将任意的合法匹配调整为更优的、满足 $i$ 只能形成 $(i,j)(j\in \{i-2,i-1,i+1,i+2\})$ 的匹配的方案。 最终只剩下三种结构：连续的三元环，例如 $(i,i+1)(i+1,i+2)(i+2,i)$ ；连续的二元环，例如 $(i,i+1)(i+1,i)$；连续的一条链，例如 $(i,i+1)(i+1,i+2)(i+2,i+3)\cdots (i+k,i+k+1)$。前两种情况有交叉，但是无法调整；并且能够发现，只有前两种情况无法调整。 #### Part 4. 你会了 然后就能考虑 dp 了：令 $f_{i,j,0/1}$ 表示目前考虑到 $i$ 的匹配 $(i,?)$，前 $i$ 个点一共有 $j$ 对匹配，目前是否在一条形如 $(u,u+1)(u+1,u+2)\cdots(i-1,i)$ 的链中。 - $f_{i,j,1}\gets f_{i-1,j-1,1}+b_{i}+b_{i-1}$，表示延续一条链，增加一对匹配，连接 $(i-1,i)$。 - $f_{i,j,1}\gets f_{i-2,j-1,0}+b_i+b_{i-1}$，表示新建一条链，增加一对匹配，连接 $(i-1,i)$。 - $f_{i,j,0}\gets f_{i-2,j-2,0}+2(b_i+b_{i-1})$，表示新增一个二元环，增加两对匹配，连接 $(i-1,i)(i,i-1)$。 - $f_{i,j,0}\gets f_{i-3,j-3,0}+2b_i+3b_{i-1}+2b_{i-2}$，表示新增一个三元环，增加三对匹配，连接 $(i-2,i-1)(i-1,i)(i,i-2)$ 或者 $(i,i-1)(i-1,i-2),(i-2,i)$。 - $f_{i,j,0}\gets f_{i-1,j,0}$，表示 $i$ 没有匹配任何点。 - $f_{i,j,0}\gets f_{i,j,1}$，表示我摆烂了，不延续一条链。 乍一看是 $O(mt)$ 的？的确是 $O(mt)$ 的。 考虑瓶颈在于强制选择 $t$ 对匹配，对于这类问题，我们可以通过证明答案随匹配数的变化具有凸性，而进行 wqs 二分。 这题的凸性十分显然，因为是匹配问题，可以转化成费用流模型： - 有超源 $S'$ 和超汇 $T'$，源点 $S$ 和汇点 $T$，$S'\to S$ 连流量 $t$，费用 $0$ 的边（以下 $u\to v$ 连流量 $f$ 费用 $w$ 的边简记为 $u\to v(f,w)$）。即 $S'\to S(t,0),T\to T'(t,0)$。 - 记 $i$ 的左部点为 $l_i$，右部点为 $r_i$，$S\to l_i(1,0),r_i\to T(1,0)$。 - 对于 $i\neq j$，$l_i\to r_i(1,S_{\max(i,j)}-S_{\min(i,j)-1})$。 不难发现最小费用最大流就是答案。根据费用流函数的凸性，原问题具有凸性，可以 wqs 二分。具体地，二分斜率 $k$，新建一对匹配时，直接减去 $k$ 的代价即可。 最终复杂度 $O(n\log V)$。代码好写得很。 ## 矩阵加速优化 ### [CF852B Neural Network country](https://www.luogu.com.cn/problem/CF852B) Difficulty : 2000 $dp$ 与矩阵快速幂优化。 考虑 dp，因为层与层之间的转移过程相同，可以快速幂。 令 $dp_{i,j}$ 表示第 $i$ 层长度 $\mod m$ 为 $j$ 的方案数。 那么 $dp_{i,j}\gets\sum dp_{i-1,j-c_k},c_k=\sum\limits_{i=1}^{n}[v_i=k]

然后你发现这是一个类似卷积的形式，快速幂优化即可。

写了很久，后面看题解才发现要把汇点和最后一层合并，不然会出错。

CF1152F2 Neko Rules the Catniverse (Large Version)

Difficulty : 3000

发现挨位考虑填哪个不太现实，考虑值域。

令 dp_{i,j,st} 表示考虑到 i，此时序列长度为 j，i-m 到 i-1 填空状态为 st 的方案数，考虑选/不选数即可：

dp_{i,j,st}\times (\text{popcount}(st)+1)\to dp_{i+1,j+1,(2st+1)\&2^m},dp_{i+1,j,(2st)\&2^m}

乘上那个 \text{popcount}(st)+1 是因为 i 只能放到 a_k=[i-m,i-1] 位置 k 的后面或者开头。

然后发现 O(n2^mk) 不太行，但是 2^m\times k 非常小，想到矩阵优化。

复杂度 O((2^mk)^3\log n) 即可。

CF755G PolandBall and Many Other Balls

Difficulty : 3200

列出转移方程就是傻鸟题了，具体地，令 f_{i,j} 为前 i 球取出 j 组的方案数，有：

f_{i,j}=f_{i-1,j-1}+f_{i-1,j}+f_{i-2,j-1}

列出 f_{i} 的 GF F_i(x)：

F_i(x)=F_{i-1}(1+x)+F_{i-2}\cdot x

这是递推，把矩阵元素改成多项式，矩阵快速幂即可。O(k\log k\log n)。

多项式优化

CF995F Cowmpany Cowmpensation

Difficulty : 2700

考虑一个 dp 的推。设 f_{u,i} 表示 u 子树中填 [1,i] 符合题目条件的方案数，此时不强制 u 选 i，所以有：

f_{u,i}=f_{u,i-1}+\prod\limits_{v\in \text{son}(u)}f_{v,i}

直接做是 O(nd) 的。考虑奇技淫巧优化。

考虑到边界情况，就是 u 为叶子时，f_{u,i}=i，这是个关于 i 的一次函数。

同时这个转移形式比较诡异，是儿子的值全部乘积然后求和。那么如果设 u 的 f_{u,i} 是关于 i 的 g_u 次函数的话，对于树上任意一个非叶节点：

\begin{aligned}g_u&=\deg \left(\prod\limits_{v\in \text{son}(u)}f_{v,i}\right)\\&=\sum\limits_{v\in \text{son(u)}}g_v\end{aligned}

由于 v 是叶子时 g_v=1，我们容易归纳出 g_u=\text{sz}_u，即 u 的子树大小。于是 f_{u,i} 是关于 i 的 \text{sz}_u 次函数。

如果 d\le n+1，直接暴力 dp；否则处理出 f_{n,1} 到 f_{n,n+1} 的值，用拉格朗日插值把 f_{n,d} 插出来即可。

复杂度 O(n^2)。

AGC020F Arcs on a Circle

Difficulty : Unavailable

先考虑只能放整点的情况，不难想到考虑 dp。

对于环上的 dp，考虑断环成链，即钦定一条线段的左端点为起点。这里我们令长度最长的线段的左端点为环的起点。

这样做有一个好处：我们不用考虑一条线段把环末尾覆盖再覆盖开头的空的情况，而当我们钦定一个长度较小的线段作为起点时，在环的末尾放一个长度较长的线段有可能覆盖到环开头的空隙中，这样是合法的，但判不到。

然后就相当于固定了一个前缀被覆盖，剩下 n-1 条线段，由于 n 的范围较小，不难想到状压。同时我们考虑从前往后枚举线段起点，这样任意时刻覆盖的都是一段前缀。具体来讲，我们设 f_{i,S} 表示覆盖了 [0,i] 这段极长前缀，用了 S 集合中线段的方案数（最长线段，即我们已经钦定位置的线段不算）。

转移时枚举线段起点 i、要填的线段 j、上一刻 S 集合的状态 T 以及上一刻覆盖到的前缀 [0,w] 即可。由于我们钦定了最长线段为起点，中途我们一旦留下了空隙以后就无法弥补了，所以 w\ge i。我们用 w 和 i+l_j 去更新现在的极长前缀，那么有：

f_{\min(c,\max(w,i+l_j)),T\cup\{ j\}}\gets f_{w,T}

然后这是只能放整点的情况，现在考虑任意实点的情况。

考虑刚才的 dp 时间复杂度 O(c^2n2^n)，发现这个时间限制相当富余，我们考虑乱搞。

具体来讲，我们将圆和弧细分成 m 段，满足 c\mid m。我们再给 l_i 和 c 乘上 \frac{m}{c}，做刚才的 dp。显然，当 m 越大时，可以取的整点就越多。当 m\to +∞ 时，我们可以认为圆环上所有实点都可以取到。

于是我们又有一个 O(m^2n2^n) 的 dp 了，其中 m\to +∞。考虑优化复杂度。

我们想起一种 dp 优化方法，在值域很大，另一维很小，答案满足为关于值域的较小次数多项式时，可以用拉格朗日插值优化。例如这题。

类似地，这题我们放大眼睛观察，我们发现任意摆放线段时，合法的方案数是一个关于 m 的 n 次多项式。当我们钦定最长线段起点时，方案数就是一个关于 m 的 n-1 次多项式但我不会证。感性理解一下，每次插入一条线段最多使次数增加 1，而一共 n-1 条线段，所以多项式次数不超过 n-1。

于是我们取 m=c,2c,\cdots,nc 即可得到这个多项式的 n 个点值，而我们要求：

\lim\limits_{m\to +∞}\frac{f(m)}{m^{n-1}}

上面是合法的方案数，下面是总方案数，除一下就是概率。同时不难发现这东西就是 [m^{n-1}]f(m)，即求最高次数项的系数。

回忆拉格朗日插值公式：

f(x)=\sum\limits_{i=1}^ny_i\prod\limits_{j\neq i}\frac{x-x_j}{x_i-x_j}

相当于若干个一次式相乘，每个一次式里面取一次项或常数项。但是由于我们要求最高次数项，我们只能取一次项，所以：

[x^{n-1}]f(x)=\sum\limits_{i=1}^ny_i\prod\limits_{j\neq i}\frac{1}{x_i-x_j}

代入 y_i=f_{ic,U} 就做完了。复杂度 O(c^2n^42^n)，其实由于钦定的最长线段，应该是 2^{n-1}，所以常数很小。

ABC331G Collect Them All

Difficulty : 2668

对于一个随机过程，令 t_i 为拿到第 i 个数的时间。那么答案就是 \mathbb{E}(\max t_i)。

板板 min-max 容斥：

\begin{aligned}\mathbb{E}(\max t_i)&=\sum\limits_{T}(-1)^{|T|+1}\mathbb{E}(\min\limits_{i\in T} t_i)\\&=\sum\limits_{T}(-1)^{|T|+1}\frac{n}{\sum\limits_{i\in T}c_i}\end{aligned}

有一个经典的背包 dp，令 f_{i,j} 表示选到 i，T 集合元素之和为 j，所有方案的 (-1)^{|T|+1} 的和，那么 f_{i,j}=f_{i-1,j}-f_{i-1,j-c_i}，答案就是 n\sum\limits_{i=0}^n\frac{f_{m,i}}{i}。

写成生成函数的形式，也就是 F(x)=-\prod\limits_{i=1}^m(1-x^{c_i})。

然后就是套路了，分治 NTT 或者 exp 后求逆均可。

状态设计优化

CF1188D Make Equal

Difficulty : 3100

有一个简单的想法，就是把所有数都加到最大值上面。

但是这个想法显然是错的，观察样例 2 知道你可以改变最大值以缩小答案。

考虑最大值被加了多少，记为 x，即求 \min\limits_{x}\{\sum\limits_{i=1}^{n}\text{popcount}(x+a_1-a_i)\}，此处假设 a 从大到小排序。

令 a_i\gets a_1-a_i，则即求 \min\limits_{x}\{\sum\limits_{i=1}^{n}\text{popcount}(x+a_i)\}。

考虑从低到高填 x，x+a_i 的第 k 位由 3 个因素决定：

前两个一个是决策一个是确定的，考虑将第 3 个因素加入 dp 状态。

然后你考虑对于每个 i\in [1,n] 记录进位/不进位，得到了一个状态 O(2^n) 的做法，您死了。

然后你发现一个性质：进位的数一定都是 a_i \mod 2^k 尽量大的数，也就是说按照 a_i 的第 k-1 位从大到小排序后，可以取来进位的一定是一段前缀（在这里我们不关心 k-1 位为 0/1 的数之间的大小关系，而只关心 k-1 位进位的个数），我们可以枚举这个在第 k-1 位的前缀。

令 cnt 为第 k 位为 1 的数的总个数，tot 表示当前前缀第 k 位为 1 的数的个数。

然后就可以考虑决策：

令 dp_{i,j} 为考虑到第 i 位，第 i-1 位有 j 次进位的最小答案（也就是前缀长度为 j），依照上面 O(n\log w) dp 即可。

AGC043C Giant Graph

我不知道这算不算 dp 优化。

由于 10^{18} 远大于 n，我们可以贪心地选择 x+y+z 尽量大的点。于是我们将 x+y+z\le x'+y'+z' 的 (x,y,z) 向 (x',y',z') 连有向边。

考虑一个 \text{dp}，令 f_{x,y,z} 表示是否选择 (x,y,z) 这个点，是则为 1，否则为 0。

显然有 f_{x,y,z}=\prod\limits_{(x,y,z)\to (x',y',z')}[f_{x',y',z'}=0]，即如果一个点的后继都不被选，我们就可以贪心地选择这个点；如果一个点地后继中有被选的，那这个点就不能被选。

这东西显然就是个博弈图。f_{x,y,z} 为 0 就是必胜态，1 为必败态。于是我们需要选择所有处于必败态的点的权值。

容易发现，这就相当于在三个图上，分别有一个点，为 x,y,z，每次选择 x,y,z 中的一个沿着有向边移动，不能移动的人输。三个图的 \text{SG} 值异或起来为 0 的话在原图上就是必败态了。

由于 \text{DAG} 上 \text{SG} 值不超过 O(\sqrt n)，可以 O(n) 枚举两个图的 \text{SG} 值 i,j，另一个图取 \text{SG} 值为 i\oplus j 的点即可。