叁

20251215

Parentheses and Swapping

推一下每个集合出现的概率，发现是若干个数的乘积。

容斥计数，所有方案减去没有出现某个集合的方案。

然后需要计算这个东西：

\[\sum_S \frac{(n!-z(S))^k}{n!^k} \]

分子二项式定理分一下，得到：

\[\sum_{i=0}^k \sum_SC_{k}^{k-i}n!^iz(S)^{i}(-1)^i \]

\(\sum z(S)\) 是 \(1~n-1\) 任意选的累乘，就是\(\Pi (j+1)\) ，\(\sum z(S)^i\) 是 \(\Pi (j^i+1)\) ，本质就是考虑第 \(j\) 个选还是不选。

字符串问题

先莫反。

定义 \(a^(d)\) 表示当 \(s_i=s_{i+d}\) 时，\(a^(d)_{i+d}=1\) 否则为 \(0\) 。

枚举周期长度 \(d\) ，用类似【优秀的拆分】的技巧，得到若干个连续1段，\(r=1\) 特殊考虑，剩下要求每个段的长度大于等于 \(d\) 。

段的个数最多为 \(\frac{n}{d}\) ，对于每一段，直接暴力枚举 \(r\) ，贡献到一个区间上，直接差分，这一部分的时间复杂度也是 \(\frac{n}{d}\)。

SA实现总复杂度 \(O(nlogn)\) ，二分+hash多个log。

Diameter of a Tree

构造。

树的直径过同一个中点。

叶子可以先填，且可确定路径的前一半，

对于后一半的一条路径，每一个点是固定的，且与儿子个数有关，

然后直接dp就可以了，每两个儿子比较是它们到叶子的距离，但每次比较必会删掉一条链，且每个点只会被删一次，复杂度 \(O(n)\)。

Random Shuffle

~Ciallo～(∠・ω<)_

Parentheses and Swapping

还是构造，还有最小化字典序。

排列是平凡的。

有一个贪心，每次尽量往后选。

这个贪心大部分情况是对的，但有一种特殊情况，当一个点的颜色是上一个点选择的颜色时，此时可以决策是否可以十字交换，

然后只用求区间最小即可。

贪心是这样的，只能感性理解。

Basic Counting Practice Problems

我谔谔。

Many Illumination Plans

Challenge NPC II

每条边描述成向量，对 \(u+1\) 对 \(v-1\)，一个图联通的条件是这样生成的行列式不为0。

你说什么？行列式还可以dp？

艹