T2
题目大意;
有一棵大小为 \(n\) 的树和 \(m\) 个关键点,你要从这 \(m\) 个关键点中随机选择 \(k\) 个点,问这 \(k\) 个点两两之间最长距离的期望是多少。
\(n \le 2000, m \le 300\)
解题思路:
最暴力的做法肯定是直接 dp,但时间复杂度是 \(O((nm)^2)\) 起步的,所以我们考虑使用 “最长距离” 的性质。
我们单独把这 \(k\) 个点的生成树抠出来,那么最长距离显然等价于直径。
我们考虑枚举 \((u,v)\) 字典序的直径,只需要计算方案数,但我们有一个特殊的性质,那就是树的直径的两个端点对于每一个点都是最远的。
那么任意一对点,你只需要判他们到我们枚举的直径是否大于直径即可。
\(O(m^3)\)。
这是本题的特殊性质,遇到 dp 复杂度太高的计数题,可以去观察 dp 的条件的特殊性来优化之间复杂度。
T3
题目大意:
有一个大小为 \(n\),边数为 \(m\) 的仙人掌,求他的邻接矩阵的行列式。
\(n \le 10^5\)
解题思路:
我们发现行列式枚举的 \(p\) 的置换环在仙人掌中必须也是环,包括二元环。
相当于从仙人掌里找到几个不交的环,算他们的贡献。
套路地,圆方树上做树形 dp。
现在唯一的难点变成了怎么算 \(2^{inv(p)}\),而且我们现在只知道每个环长,希望对他俩进行一个转化。
考虑在一个排列中,每次交换任意两个相邻的数会将逆序对变化 1,而且也会对置换环的个数变化 1。
由于 \(-1\) 的幂只和奇偶性有关系,所以我们发现 \((-1)^{inv(p)} = (-1)^{n - cyc(p)}\)。
\(O(n)\)。
这题最后一步还是很有意思的,就是如何将我们未知的转化成我们已知的。
T4:
题目大意:
你要将 \(n\) 个石子分到 \(k\) 堆里,然后两人流操作,每个人可以选择至少一堆,至多 \(m\) 堆并取任意数量的石子,求第一个人获胜的不同的分法。
\(n \le 10^4, k \le 10^3\)。
解题思路:
还是太不敢猜了。
考虑 \(m = 1\) 时,就是经典 \(Nim\) 游戏,然后你设 \(dp_{i,j,0/1}\) 表示考虑了二进制前 \(i\) 位,和为 \(j\),异或值是否不为 0 的方案数。
然后我们希望将 \(nim\) 的结论推广出去,先考虑最经典的 \(nim\)。
我们胜利的条件为:他们整体的二进制位下,并非每一位的 1 的出现次数为 2 的倍数的方案。
那么考虑将 \(2\) 替换成 \(m + 1\),这就是这个题。