CF1970G3 Min-Fund Prison (Hard)
添加的边肯定是固定的，为连通块个数 \(-1\)。跑个边双，问题转换成给一些数，可以把其中一个数分裂成两个（这两个数之和为原数），再分成两个集合 \(A,B\)，使得集合 \(A\) 的权和的平方加 \(B\) 权和的平方最小。
可以用背包 DP 出第一个集合 \(A\) 的权和，设 \(f_i\) 为集合 \(A\) 的权和为 \(i\) 是否可行，用 \(\text{bitset}\) 加速。
key：树是二分图，所以最大匹配是最小点覆盖。
于是枚举最小点覆盖集合，这样就能确定选了哪些边了（选的边的端点至少要有一个在点覆盖集合中）。
拿这些边跑一个 Kruskal，如果选的边少于 \(n-1\) 那这个点覆盖就不合法，否则取最小值就是答案。
key：对于为积和形式的矩阵，可以将其分解再利用结合律“缩小”矩阵。
DP：\(f(i,u)\) 为到了第 \(i\) 天，走到叶子 \(u\) 的方案数。
\[f(i,u)=\sum_vf(i-1,v)\times (s_u(s_v+l_v)+l_us_v) \]考虑优化。
\[f(i,u)=\sum_vf(i-1,v)\times (s_us_v+s_ul_v+l_us_v) \]设 \(w_u=s_u+l_u\)，则有：
\[f(i,u)=\sum_vf(i-1,v)\times (w_uw_v-l_ul_v) \]写出其转移矩阵
\[\begin{bmatrix}f(i,1) \\f(i,2) \\\vdots \\f(i,m) \end{bmatrix}= \begin{bmatrix} w_1w_1-l_1l_1& w_1w_2-l_1l_2& \cdots & w_1w_m-l_1l_m \\ w_2w_1-l_2l_1& w_2w_2-l_2l_2& \cdots & w_2w_m-l_2l_m \\ \vdots & \vdots & \ddots & \vdots \\ w_mw_1-l_ml_1& w_mw_2-l_ml_2& \cdots & w_mw_m-l_ml_m \end{bmatrix} \begin{bmatrix}f(i-1,1) \\f(i-1,2) \\\vdots \\f(i-1,m) \end{bmatrix}\]注意到转移矩阵有：
\[\begin{bmatrix} w_1w_1-l_1l_1& w_1w_2-l_1l_2& \cdots & w_1w_m-l_1l_m \\ w_2w_1-l_2l_1& w_2w_2-l_2l_2& \cdots & w_2w_m-l_2l_m \\ \vdots & \vdots & \ddots & \vdots \\ w_mw_1-l_ml_1& w_mw_2-l_ml_2& \cdots & w_mw_m-l_ml_m \end{bmatrix} = \begin{bmatrix} w_1 &l_1\\ w_2 &l_2\\ \vdots & \vdots\\ w_m &l_m \end{bmatrix} \begin{bmatrix} w_1 &w_2&\cdots &w_m\\ -l_1 &-l_2&\cdots &-l_m \end{bmatrix} \]换元：
\[A=B\times C \]于是答案为：\(A^n=(BC)^n=B(CB)^{n-1}C\)。
最后一次矩阵乘法只用算第一列不然会炸。
CF1970B3 Exact Neighbours (Hard)
构造题。
如果存在 \(a_i=0\) 的，说明这个房子放哪都可以。那么把 \(a_i=0\) 的放在左上角，其余的按 \(a\) 从大到小排序，排成一个堆之字型，每一个房子都指向前面一个。
如果存在 \(a\) 相等的一对，把它们放在左边两列形成互相依赖，并且第二个在第二列的第一行。剩下的也排序后按之字型。
否则，\(a\) 是一个 \(1\sim n\) 的排列。排序后前面的按之字型，每一个都指向后面一个，剩下的 \(1,2,3\) 可以简单构造让它们互相依赖。
标签：2w,1w,cdots,bmatrix,2l,杂题,vdots From： https://www.cnblogs.com/includec/p/18212765