184 P9005 [RC-07] 超超立方体
两个图笛卡尔积的 Laplace 特征值为两个图特征值集合中任选一个相加的所有可能值。题目里的超立方体就是若干完全图的笛卡尔积。
一张完全图的 Laplace 矩阵 \(A\) 形为对角线 \(n-1\)，其余位置 \(-1\)，而 \(nI-A\) 为全 \(1\) 矩阵，全 \(1\) 矩阵秩为 \(1\)，所以只有一个非零特征值，而迹为 \(n\) 因此另一个为 \(n\)。由全 \(1\) 矩阵的特征值作用 \(n-x\) 后得到完全图的 Laplace 矩阵：\(n-1\) 个 \(n\) 与一个 \(0\)。
矩阵树定理事实上说的是，生成树数量等于 Laplace 矩阵特征值之积除以点数。而我们可以通过特征值数量计算生成树数量：
\[\frac{\prod_{S\in\{1,2,\cdots,n\}}(\sum_{i\in S}a_i)^{\prod_{i\in S}(a_i-1)}}{\prod_{i=1}^n a_i} \]使用背包计算一下就好了，复杂度 \(O(n^2\max a_i)\)。
185 CF1781H2 Window Signals (hard version)
枚举一下包含灯的最小矩形大小 \(a\times b\)，容斥一下四个边界是否有灯。
零个、一个 ban 位置都弱于两个的情况，我们不妨只考虑两个。
很容易让两个灯翻折成左下、右上关系，正难则反，我们计算任意两个对应位置都有一个灯的图案数量。
可以形成若干链，每条链相邻至少选一个，系数就是斐波那契数，没有限制的就是二的次幂，直接 \(O(n^2)\) 计算就可以 \(O(n^4)\)，事实上可以过 Hard Version。
事实上枚举链开头的一维，长度数量是 \(O(1)\) 种，仔细算算应该就是 \(O(n^3)\) 了。
标签：特征值,裁切,33,矩阵,数量,2023,prod,Laplace From： https://www.cnblogs.com/xiaoziyao/p/17091130.html