目录
- [AGC070B] Odd Namori
- [JOI Open 2025] 冒泡排序机 / Bubble Sort Machine
- [AGC039F] Min Product Sum
[AGC070B] Odd Namori
Matrix-Tree 定理：给一张带权有向图 \(G\)，求 \(G\) 所有以 \(1\) 为根的内向生成树边权之和 .
看成给每个点 \(i\ge2\) 选一个出边 \(p_i\)，不能连自环，求 \((1-1)^{\#\mathrm{cycle}}\) 之和，也就是相当于钦定若干环贡献 \(-1\) . 直接分析 Kirchhoff 矩阵 \(L=D-A\) 的行列式就相当于是选一个排列 \(\pi\)，不是自环的部分贡献边权（这些部分相当于钦定的环），自环部分乱连 . 由于交换一次排列奇偶性改变所以逆序对个数的奇偶性和 \(n-\#\mathrm{cycle}\) 的奇偶性是一样的，最后加上 \(A\) 上的负号的贡献，容斥系数正好是 \((-1)^{\#\mathrm{cycle}}\) .
对于原题来说相当于算 \((1+1)^{\#\mathrm{odd}}(1-1)^{\#\mathrm{even}}\)，学习 Matrix-Tree 定理可以发现其实是算 \(\det(D+A)\) .
构造这样一个图（以下所有 \(i\in[2,n]\)）：\(1\xrightarrow{-1}i,\,i\xrightarrow{n}1,\,i\xrightarrow{1}p_i,\,i\xrightarrow{-2}0,\,1\xrightarrow{2n}0\) . 由 Matrix-Tree 定理可知就是要算以 \(0\) 为根的内向生成树边权和 .
接下来先选树边，然后讨论 1 连 0 还是连树上的点，把贡献拆到树上就可以得到答案的表达式了 .
[JOI Open 2025] 冒泡排序机 / Bubble Sort Machine
一个前缀 \([1,x]\) 经过 \(c\) 轮冒泡后得到的序列相当于 \([1,x+c]\) 的前 \(x\) 小值，然后就随意维护了 .
[AGC039F] Min Product Sum
一、行 min 和列 min 是 \(a_i,b_j\)，那么就是要求 \(\prod_{i,j}\min(a_i,b_j)\) 之和 . 从小到大填，每轮分步转移行 / 列，min 需要容斥一下才能做 .
二、考虑改成数 \((A,B)\) 使得 \(A\) 的行 max 不大于 \(B\) 的行 min 且 \(A\) 的列 max 不大于 \(B\) 的列 min，从小到大填 \(A\) 的行 max 和 \(B\) 的列 min，每轮分步转移行 / 列，这样就能做了 .