- 「CTT 2020 Day1 T1」术树数
- 「CTT 2020 Day1 T2」树数术
- 「CTT 2018 Day1 T3」芒果冰加了空气
- 「CTT 2018 Day2 T3」Wechat
- 「CTT 2019 Day1 T1」递增树列
- 「CTT 2020 Day2 T2」随机游走
随缘做。按通过时间顺序写。可能会有点意识流。Orz Qiuly！！！！
「CTT 2020 Day1 T1」术树数
根据「WC2011」最大 XOR 和路径等经典题，我们知道关键就是随便选取一棵生成树，并求出所有简单环的线性基。
题目的修改操作天然给了我们一棵生成树。
考虑 \(k\) 进制线性基如何实现。首先我们采用辗转相除法消元，并且我们希望线性基上主元的位置都是 \(k\) 的约数。这是因为，我们应该用基中每个向量的整数倍数来刻画所有张成的向量（而不应该溢出到 \(k\)）。
但是另外一个问题又会出现：在模 \(k\) 意义下，某一主元以特定值被表出的方案并不唯一。我们认为这是熟知结论：连边 \((x, (x+v)\bmod k)\) 会形成 \(\gcd(k, v)\) 个大小为 \(k/\gcd(k, v)\) 的环。因此，我们考虑在插入主元位置后，将向量乘上 \(k/\gcd(k, v)\)，其中 \(v\) 是主元位置的值。如此再向下插入即可。
查询的时候，我们在主元位置不超过 \([0, k-1]\) 的范围内尽可能多加/减向量即可求得最值。
可能很抽象，不如看提交记录。
「CTT 2020 Day1 T2」树数术
简单题。先写个 ST 表支持 \(O(1)\) 查询 LCA，再写个 ST 表支持 \(O(1)\) 区间 LCA。
考虑 \(k=1\)，我们只需要套路地二分出 \(pre_i\) 即可转化为数点问题。而 \(k>1\) 的时候，逐个区间处理，相当于在整个区间前面插入了一个特殊点，那只会导致区间的贡献出现一个分界（即，第一个是其祖先的点），二分出来即可。用 ST 表可以把二分改成倍增。
「CTT 2018 Day1 T3」芒果冰加了空气
考虑连一条边 \((u, v)\) 导致点分树合并的过程，事实上与一般的数据结构合并是一致的：传入两个根结点，并考虑选择一个成为最后的根结点，将剩下的部分沿着 \(u, v\) 所在的链递归。
因此，我们只需要记状态 \(f_{u, i}\) 表示 \(u\) 子树内的点分树，\(u\) 的深度为 \(i\) 的方案数。
「CTT 2018 Day2 T3」Wechat
(ans(洛谷5825) /= fac[n]).pop_back();
「CTT 2019 Day1 T1」递增树列
首先，可以证明，所有 \(\operatorname{lca}(p_i, p_{i+1})\) 都具有祖先后代关系。否则，显然可以找到一个分界点不满足条件。
那么直接设 \(f_{u, i}\) 表示 \(u\) 子树内选择 \(i\) 个点的方案数。转移的时候需要将其他子树的点与之合并，需要算一个限制某些点不能相邻的排列数。可以直接 DP 也可以容斥。
时间复杂度 \(O(n^4)\)。
「CTT 2020 Day2 T2」随机游走
首先转切比雪夫距离，那么答案就是 \(2n\) 个 \([-1/2, 1/2]\) 上的均匀随机实数的和的绝对值的期望。
给每个变量平移 \(1/2\)，考虑 \(2n\) 个 \([0, 1]\) 上的实数的和 \(< x\) 的概率。根据经典容斥，我们知道这就是
\[ \sum_{k=0}^{\lfloor x\rfloor} (-1)^k \binom{2n}k \frac{(x-k)^{2n}}{(2n)!} \]
我们考虑将这个函数在 \([n, 2n]\) 上积分，那么可以感受到一组和为 \(x\) 的序列的权值应该是 \(\min(n, 2n-x)\)。
从而求出这个之后，只需要用 \(n\) 减去其，就得到了原问题 \(>0\) 部分的期望。乘二即可得到答案。
而求其在 \([n, 2n]\) 上的积分可以考虑交换求和与积分号，
\[ \begin{aligned} &\quad\; \int_n^{2n} \sum_{k=0}^{\lfloor x\rfloor} (-1)^k \binom{2n}k \frac{(x-k)^{2n}}{(2n)!} \,\mathrm dx \\ &= \sum_{k=0}^{2n} \frac{(-1)^k}{k!(2n-k)!} \int_{\max(k, n)}^{2n} (x-k)^{2n} \,\mathrm dx \\ &= \sum_{k=0}^{2n} \frac{(-1)^k}{k!(2n-k)!} \int_{\max(0, n-k)}^{2n-k} x^{2n} \,\mathrm dx \\ &= \sum_{k=0}^{2n} \frac{(-1)^k}{k!(2n-k)!} \left(\left.\frac{x^{2n+1}}{2n+1}\right|_{\max(0, n-k)}^{2n-k}\right) \end{aligned} \]
阶乘逆元和所有 \(j^{2n+1}\) 都可以线性预处理。