一些杂题

一些杂题的题解。

bzoj3457 Ring

由Polya定理，答案为 $\frac{\sum_{i=1}^nF(\gcd(n,i))}{n}=\frac{\sum_{d|n}\varphi(d)F(\frac{n}{d})}{n}$。其中 $F(m)$ 为长度为 $m$ 的循环项链上含该字符串 $S$ 的方案数。

$F(m)$ 的计算使用容斥，用 $2^m$ 减去不含 $S$ 的方案。设 $f_{i,j}$ 为当前长度为 $i$，匹配到第 $j$ 位的方案数。

假设最后一位填完后，匹配到字符串第 $i$ 位，那么初始条件为 $f_{0,j}=[i==j]$。答案为 $f_{n,i}$。

$f_i$ 转移到 $f_{i+1}$ 相当于乘以一个矩阵 $A$，其系数可用KMP算出。

先算出 $A^m$，然后枚举 $i$，暴力计算即可。

可以通过预处理 $A^{\sqrt{n}i},A^i$ 降低算 $A^m$ 的复杂度。

时间复杂度 $O(d(n)k^3)$。

bzoj2353 矩形压缩

先离散化。

显然，这些矩形要越小越好，如果 $A$ 包含 $B$，那么选 $B$ 一定更优。

于是只需要考虑如何找到所有的极小的长方形。

哈希，对每个原来的长方形随机一个值，对长方形内部的整点的权值异或上该值。

对于每个点找到四联通内所有权值相同的点，如果形成的形状是个矩形，则说明找到一个。

剩下的是裸的二分图带权匹配。