swift's blog

识别子串

可以容易用后缀自动机+双指针求出从每一位开始最少走几位能使这个串只出现过一次，发现每一位的答案只能是覆盖它的最短的串或者是离它左边最近的不覆盖它的串，写个线段树+前缀最大值就行。

bzoj 4894

矩阵树定理模版。

code: /code/2022.4.11/bz4894.cpp

【BJOI2014】欧拉

设 $x=\prod p_i^{k_i}$，则 $\phi(x)=\prod p_i^{k_i-1}(p_i-1)$,前边一部分指数可能为0，所以枚举 $y$ 的因数找出所有可能的 $p_i-1$，然后把所有 $p_i$ 从大到小排序（为了尽快找到交优解）后 dfs 即可。

CF464D

【GDOI2013】飞行棋

题面写的十分复杂，我甚至没弄明白开始节点在那个图上是哪 /yun

CF494C

P3232

AT3981

发现与 1 直接比赛的实际上有 n 组人中的最小值，每组分别有 $2^0$ 到 $2^{n-1}$ 个人并且在原序列上连续，考虑如果我们算出了每组的成员以及顺序的方案数，那么把 1 放在每个位置上都能唯一的确定这些组怎么放，于是将方案数乘上 $n$ 就是答案。

AT4352

考虑容斥，答案就是 $\sum_{S \in E} (-1)^{|S|}f(S)$

其中 $f(S)$，是对于断开 S 后的所有联通块内随便配对的方案数。

AT4362