THUSCH 2017 做题记录
巧克力
很好的 随 机 化 斯坦纳树题。首先如果 $C$ 很小的话怎么做？我们可以二分中位数（变权值为 $0$/$1$） + 状压跑斯坦纳树。但是我们首要的是选的块数尽量少，次要的是选的 $0$ 尽量多，怎么 $dp$？这里有个超好的 Trick：把 $0$ 赋为 $inf - 1$，把 $1$ 赋为 $inf + 1$，块数就是 $\lfloor \frac{val + 300}{1000} \rfloor$
但是 $C$ 大而 $K$ 小。于是想到把 $C$ 种颜色随机分为 $K$ 类跑状压。正确率是 $\frac{k!}{k^k}$，约等于 $0.0384$, 跑个几百次就没问题了。
杜老师
思索良久，无果
打开题解 -> 线性基 -> 关闭题解，仔细思考.png
- $> \sqrt{r}$ 的特殊处理？
- $< \sqrt{r}$ 的，存为质因子分解后指数奇偶性的二进制数，那么问题就是问有多少个子集异或和为 $0$。
卡 壳
打开题解。
任意线性基外的一种取法都能在线性基内选一种取法使得两者异或为 $0$，因此方案数为 $2^{r - l + 1 - 线性基大小}$
神必了神必了！
$> \sqrt{r}$ 的记录一下，对于之后所有有该因子的数都异或上。
设 $f(r)$ 表示小于 $r$ 的素数个数。这样复杂度是 $O(\frac{r - l + 1}{\omega} f^2(\sqrt{r}))$，无法通过。
题解说：暴力验证 $r - l + 1 > 6661$ 时一定会满，即线性基大小为 $l$、$r$ 出现的质因子个数，因此复杂度为 $O(f(r) + \frac{6661}{\omega} f^2(\sqrt{r}))$
对不起这谁想得到啊 fxck
换桌
裸的 KM $O(n^3m^3)$（还不会）
注意到 $m$ 很小
可以考虑优化连边什么的？比如相邻座位间连边，每个座位上开两棵线段树，表示向左走和向右走，共 $2m$ 棵。线段树上的边带有权值。到达线段树上某个节点，默认在端点。
点、边都是 $nmlog$，需要多路增广（就是 UNR-白鸽 那道，dinic 一起跑，把残量网络上余量增广掉）需要打 $vis$ 标记，因为可能有 $0$ 环
大魔法师
所有操作都可以用 $x = x * a + b$ 的形式来替代，线段树维护矩阵即可。$O(4^2 q logn)$
不加「乘向量」的优化直接艹过去了，我就是传说中的小常数选手吗（划，可能是开了 Ofast 的缘故罢
如果奇迹有颜色
这题比洛谷上的 Polya 模板题多了个相邻 $m$ 项颜色不能全不同的限制。
$|X/G| = \frac{1}{|G|} \sum_g m^{c(g)} = \frac{1}{|G|} \sum_k \varphi(n / k) * f(k)$
现在要算 $f(gcd = k)$ 的染色方案数。可以状压计算，状态数是 $m^{m}$，直接跑矩阵快速幂能拿到 $55$ 分的好成绩，然后我就不会了
题解告诉我要去学常系数齐次线性递推，我就滚去学了。厚厚，新知识！（于是就有了这篇拼凑起来的笔记
猜测递推式长度小于 $m^{m}$，借助超能力（打表）发现 $m = 7$ 就 $409$.
宇宙广播
咕了