老年选手康复训练

学考考完了。虽然身为d类咸鱼选手还是要好好备战一下noi的。

从今天开始进行康复训练，不过白天应该还是要肝文化课。等过几天训练时间应该会多一点。

[CTS2019]随机立方体

这道题现在做了一遍好像有一点sibo啊，可能是考试的时候太紧张了吧。

题意就不写了。

题目要求恰好 $k$ 个，那我们考虑用至少含 $i$ 个进行容斥。

那么容斥系数 $f_{i}$ 需要满足：

[i = k] = \sum_{j = 0}^{i} (\binom{i}{j}) f_{j}

进行二项式反演，得到：

f_{i} = \sum_{j = 0}^{i} (- 1)^{i - j} (\binom{i}{j}) [j = k]

即：

f_{i} = (- 1)^{i - k} (\binom{i}{k})

由于在 $i < k$ 时 $(\binom{i}{k})$ 等于 $0$ ，因此上面的式子是良定义的。

那么考虑如何计算至少含 $i$ 个极大数的概率。

首先极大数的行号、列号、bule号（bule代表第三维的名称）一定不是相同的。

比较关键的一点是，我们可以注意到任何钦点 $i$ 个两两坐标全不同的格子为极大数的概率都是相同的。于是我们可以找一个比较特殊的位置计数，比如让他们的坐标为 $(1, 1, 1)$ ， $(2, 2, 2)$ ， $\dots$ ， $(i, i, i)$ 。同时我们钦点 $a_{1, 1, 1} < a_{2, 2, 2} < \dots < a_{i, i, i}$ 。

思考一下，可以发现如果我们只观察至少有一维横坐标 $\leq i$ 的格子， $(i, i, i)$ 一定是其中的最大值。如果我们只观察至少有一维横坐标 $\leq i - 1$ 的格子， $(i - 1, i - 1, i - 1)$ 一定是其中的最大值。以此类推即可。不难发现只要满足上述条件，那么这个方案一定合法。

我们设 $a_{i}$ 表示所有横坐标至少有一维 $\leq i$ 的格子数。那么满足之前所述条件的概率就是：

\prod_{j = 1}^{i} \frac{1}{a_{j}}

同时还要注意，这只是我们钦点的位置和大小关系之后的答案，所有合法的选取位置和大小关系的方案共有 $(\binom{n}{i}) (\binom{m}{i}) (\binom{l}{i}) * (i!)^{3}$ 种，其组合意义是分别选出三维的横、纵、bule坐标，再决定大小关系。

后面的方案数可以用预处理阶乘及逆元实现 $O (1)$ 计算，之前的概率，则可以通过线性求逆元均摊 $O (1)$ 计算。于是做一组数据就是 $O (n)$ 的，总复杂度 $O (T n)$ 。

[CTS2019]珍珠

F (x) = \sum_{i \geq 0} \frac{[i mod 2 = 1]}{i!} x^{i} = \sinh (x) = \frac{e^{x} - e^{- x}}{2}

G (x) = \sum_{i \geq 0} \frac{[i mod 2 = 0]}{i!} x^{i} = \cosh (x) = \frac{e^{x} + e^{- x}}{2}

A n s = \sum_{k = 0}^{n - 2 m} (\binom{D}{k}) n! [x^{n}] F^{k} G^{D - k}

用二项式定理把 $F^{k}$ 和 $G^{D - k}$ 展开，可以得到：

A n s = \frac{1}{2^{D}} \sum_{k = 0}^{n - 2 m} \sum_{i = 0}^{k} \sum_{j = 0}^{D - k} (\binom{D}{k}) (- 1)^{k - i} (\binom{k}{i}) (\binom{D - k}{j}) (2 (i + j) - D)^{n}

A n s = \frac{1}{2^{D}} \sum_{k = 0}^{n - 2 m} \sum_{i = 0}^{k} \sum_{j = 0}^{D - k} \frac{D! (- 1)^{k - i} (2 (i + j) - D)^{n}}{(k - i)! i! (D - k - j)! j!}

A n s = \frac{1}{2^{D}} \sum_{k = 0}^{n - 2 m} \sum_{i = 0}^{k} \sum_{j = 0}^{D - k} \frac{(2 (i + j) - D)^{n} D!}{(i + j)! (D - (i + j))!} * \frac{(i + j)!}{i! j!} * \frac{(- 1)^{k - i} (D - (i + j))!}{(k - i)! (D - k - j)!}

A n s = \frac{1}{2^{D}} \sum_{k = 0}^{n - 2 m} \sum_{i = 0}^{k} \sum_{j = 0}^{D - k} (2 (i + j) - D)^{n} (\binom{D}{i + j}) (\binom{i + j}{i}) (- 1)^{k - i} (\binom{D - (i + j)}{k - i})

A n s = \frac{1}{2^{D}} \sum_{k = 0}^{n - 2 m} \sum_{i + j = 0}^{D} (2 (i + j) - D)^{n} (\binom{D}{i + j}) \sum_{i = 0}^{k} (\binom{i + j}{i}) (- 1)^{k - i} (\binom{D - (i + j)}{k - i})

考虑 $[x^{i}] (1 + x)^{n} = (\binom{n}{i})$ ， $[x^{i}] (1 - x)^{n} = (- 1)^{i} (\binom{n}{i})$ 。

因此

(\binom{i + j}{i}) = [x^{i}] (1 + x)^{i + j}, (- 1)^{k - i} (\binom{D - (i + j)}{k - i}) = [x^{k - i}] (1 - x)^{D - (i + j)}

\sum_{i = 0}^{k} (\binom{i + j}{i}) (- 1)^{k - i} (\binom{D - (i + j)}{k - i}) = \sum_{i = 0}^{k} ([x^{i}] (1 + x)^{i + j}) * ([x^{k - i}] (1 - x)^{D - (i + j)}) = [x^{k}] (1 + x)^{i + j} (1 - x)^{D - (i + j)}

A n s = \frac{1}{2^{D}} \sum_{k = 0}^{n - 2 m} \sum_{i = 0}^{D} (2 i - D)^{n} (\binom{D}{i}) [x^{k}] (1 + x)^{i} (1 - x)^{D - i}

设 $a_{i} = \frac{(2 i - D)^{n} (\binom{D}{i})}{2^{D}}$ ，

A n s = \sum_{k = 0}^{n - 2 m} \sum_{i = 0}^{D} a_{i} [x^{k}] (1 + x)^{i} (1 - x)^{D - i}

A n s = \sum_{k = 0}^{n - 2 m} [x^{k}] (\sum_{i = 0}^{D} a_{i} (1 + x)^{i} (1 - x)^{D - i})

考虑先把 $\sum_{i = 0}^{D} a_{i} (1 + x)^{i} (1 - x)^{D - i}$ 算出来，最后一个个加。

至于这个，可以使用分治fft大法。

~~什么一个log，分治fft天下第一。~~

[CTS2019]氪金手游

现在想想怎么又比较简单啊。

考虑把关系树随便钦点一个当根。

由于正向边（向儿子连的边，表示必须早于儿子）和反向边同时存在，因此比较麻烦。考虑用容斥将反向边变为正向边，即：选出一个反向边子集 $S$ ，强制这些边必须被违反，其余反向边随意。注意正向边是永远需要满足的。计算得这样计算出的方案有 $(- 1)^{| S |}$ 的贡献。

对于一种选法，原树用正向边分成了若干联通块。对于一个点 $i$ ，设 $s_{i}$ 表示是它的子树中的点的集合。如果只考虑这棵子树，我们显然要满足 $i$ 是第一个被抽出来的，概率就是 $\frac{w_{i}}{\sum_{j \in s_{i}} w_{j}}$ ，接下来可以分成若干子树递归。

那么若干种方案就可以合起来算概率了。我们设 $d p_{i, j}$ 表示以 $i$ 为根的子树，当 $(\sum_{k \in s_{i}} w_{k}) = j$ 时，目前满足所有条件的情况乘以他们的系数的概率和。转移比较容易得到。

[ZJOI2019]开关

这真是一道好题，被送退役得心服口服。

先说几个结论：

我们设 $\tilde{f}$ 表示集合幂级数 $f$ 在快速沃尔什变换( $FWT$ )后的形式。

那么：

[x^{S}] \tilde{f} = \sum_{T} (- 1)^{| S \cap T |} [x^{T}] f

从 $FWT$ 的意义中可以看出。

\sum_{T} (- 1)^{| S \cap T |} = 2^{n} [S = \emptyset]

其中 $n$ 代表全集的大小。这和子集容斥的原理是相似的。

\sum_{T} [x^{T}] \tilde{f} = 2^{n} [x^{\emptyset}] f

用前一个式子不难证明。

现在说题目的解法。

根据题目描述，我们设 $[x^{S}] f$ 表示第一次到达状态 $S$ 的期望步数。为了分析方便，我们也可以将其看成是从状态 $S$ 到空集的期望步数。那么对于 $S \neq \emptyset$ ，我们就有：

[x^{S}] f = (\sum_{i} \frac{p_{i}}{\sum_{j} p_{j}} [x^{S Δ {i}}] f) + 1

为了更方便的表达这个式子，我们设形式幂级数 $g$ ，其中当 $S = {i}$ 时， $[x^{S}] g = \frac{p_{i}}{\sum_{j} p_{j}}$ ，否则 $[x^{S}] g = 0$ 。

于是上式可以表达为：

f = (\sum_{T} x^{T}) + f g + c x^{\emptyset}

其中 $c$ 是某个不确定的系数，起到补偿 $\emptyset$ 不符合该式的作用。我们尝试进行 $FWT$ ，对于 $\sum_{T} x^{T}$ ，它是 $x^{\emptyset}$ 进行 $FWT$ 后的结果，因此其 ${FWT}^{- 1}$ 的结果为 $x^{\emptyset}$ ，所以其 $FWT$ 后的结果为 $2^{n} x^{\emptyset}$ 。因此：

[x^{S}] \tilde{f} = 2^{n} [S = \emptyset] + [x^{S}] \tilde{f} [x^{S}] \tilde{g} + c

(1 - [x^{S}] \tilde{g}) [x^{S}] \tilde{f} = 2^{n} [S = \emptyset] + c

考虑 $[x^{\emptyset}] \tilde{g} = \sum_{i} \frac{p_{i}}{\sum_{j} p_{j}} = 1$ ，因此将 $S = \emptyset$ 代入上式可得 $c = - 2^{n}$ 。

那么对于 $S \neq \emptyset$ ，就有：

[x^{S}] \tilde{f} = - \frac{2^{n}}{1 - [x^{S}] \tilde{g}}

代入 ${FWT}^{- 1}$ 的式子中，我们就有：

[x^{S}] f = \frac{1}{2^{n}} (\sum_{T} (- 1)^{| S \cap T |} [x^{T}] \tilde{f}) = \frac{[x^{\emptyset}] \tilde{f}}{2^{n}} - (\sum_{T \neq \emptyset} (- 1)^{| S \cap T |} \frac{1}{1 - [x^{T}] \tilde{g}})

而由于 $[x^{\emptyset}] f = 0$ ，根据之前的结论， $\sum_{T} [x^{T}] \tilde{f} = 0$ ，所以 $[x^{\emptyset}] \tilde{f} = - (\sum_{T \neq \emptyset} [x^{T}] \tilde{f}) = \sum_{T \neq \emptyset} \frac{2^{n}}{1 - [x^{T}] \tilde{g}}$

因此：

[x^{S}] f = \frac{1}{2^{n}} (\sum_{T} (- 1)^{| S \cap T |} [x^{T}] \tilde{f}) = (\sum_{T \neq \emptyset} \frac{1}{1 - [x^{T}] \tilde{g}}) - (\sum_{T \neq \emptyset} (- 1)^{| S \cap T |} \frac{1}{1 - [x^{T}] \tilde{g}})

[x^{S}] f = \sum_{T \neq \emptyset} [| S \cap T | \equiv 1 (mod 2)] \frac{2}{1 - [x^{T}] \tilde{g}}

代入 $[x^{T}] \tilde{g} = \sum_{i} (- 1)^{[i \in T]} \frac{p_{i}}{\sum_{j} p_{j}}$ ，得 $1 - [x^{T}] \tilde{g} = \sum_{i} [i \in T] \frac{2 p_{i}}{\sum_{j} p_{j}}$ ，回代入原式，得：

[x^{S}] f = \sum_{T \neq \emptyset} [| S \cap T | \equiv 1 (mod 2)] \frac{\sum_{j} p_{j}}{\sum_{i \in T} p_{i}}

[x^{S}] f = (\sum_{j} p_{j}) * (\sum_{T \neq \emptyset} [| S \cap T | \equiv 1 (mod 2)] \frac{1}{\sum_{i \in T} p_{i}})

由于 $\sum_{j} p_{j}$ 非常小，因此后面的式子可以通过简单的 $d p$ 计算出来。

[ZJOI2019]语言

考场上只会写3个 $\log$ 的我太菜了。

考虑对于一个点，它能交流的所有点就是经过它的链的并。

我们可以用线段树来维护一个点集的连通并的点数（即最小的使得某些点都在内的连通块的点数），具体做法不讲了（想必这篇博客没有人看的233，如果有人问再加上去吧）。再用树上差分思想，在点上添加事件，加上线段树合并，就做完了。

虽然是一个 $\log$ 的但我写出来跑的有点慢，可能我太菜了。

LOJ #575 不等关系

一道不算很难的容斥题。

考虑最简单的容斥方法，用 $至少违背零个大于号 - 至少违背一个大于号 + 至少违背两个大于号 \dots$ 来计算，对于至少违背 $k$ 个大于号的方案数，可以发现当我们选定了哪些位置违背以后，限制就只剩下小于号了。此时长度为 $n + 1$ 的排列会被分成 $m$ 部分，大小分别为 $a_{1}, a_{2}, \dots, a_{m}$ ，每一段内要满足大小递增。那么此时的答案就是：

(\binom{n + 1}{a_{1}, a_{2}, \dots, a_{m}}) = \frac{(n + 1)!}{\prod_{i = 1}^{m} a_{i}!}

$(n + 1)!$ 对于所有方案都是相同的，我们可以不管它。于是只要将所有段的大小的阶乘的逆元相乘就是方案数。

首先考虑暴力做法，我们根据字符串 $s$ 先将排列划分为 $m$ 段，大小分别为 $a_{1}, a_{2}, \dots, a_{m}$ （这和上面的定义不一样，只是我懒得换字母了），由于容斥的关系，一些段可能会并起来。我们假定违背了其中 $k$ 个大于号，合并后段的大小分别为 $b_{1}, b_{2}, \dots, b_{m - k}$ ，那么这种方案的贡献为 $(- 1)^{k} (\prod_{i = 1}^{m - k} \frac{1}{b_{i}!})$ 。

那么考虑 $d p$ ，我们设 $f_{i}$ 表示只考虑前 $i$ 段，所有方案的贡献和。设 $S_{i}$ 表示 $a$ 的前 $i$ 项和。那么我们只要枚举第 $i$ 段会与前面的几段合并，就可以得出方程：

f_{i} = \sum_{j = 0}^{i - 1} (- 1)^{i - j + 1} f_{j} \frac{1}{(S_{i} - S_{j})!}

就得到了 $O (n^{2})$ 的做法。

可以注意到，由于和式中的最后一项非常复杂，因此很难优化成卷积形式。我们考虑更换一种方法，改设 $f_{i}$ 表示只考虑排列的前 $i$ 个，所有方案的贡献和。值得注意的是如果 $i$ 和 $i + 1$ 之间是小于，即原本在一段内的，那么我们可以任意取 $f_{i}$ 的值，因为我们将看到它对后面是没有影响的。我们再设 $a_{i}$ 表示 $i$ 和 $i + 1$ 之间是否用大于号连接（即可以断开），特别的， $a_{0} = a_{n + 1} = 1$ 。设 $S_{i}$ 表示 $a$ 的前 $i$ 项和。

根据之前的思路，易得：

f_{i} = \sum_{j = 0}^{i - 1} (- 1)^{S_{i} - S_{j} + 1} a_{j} f_{j} \frac{1}{(i - j)!}

变化一下，得：

(- 1)^{S_{i}} f_{i} = \sum_{j = 0}^{i - 1} (a_{j} (- 1)^{S_{j}} f_{j}) * (- \frac{1}{(i - j)!})

可以发现，虽然其转化为简单的卷积式比较困难，但是借助分治fft，我们就可以先将 $(- 1)^{S_{i}} f_{i}$ 算出来，再乘上 $a_{i}$ 贡献给后面了。复杂度 $O (n \log^{2} n)$ 。

所以说，分治fft天下第一。