Atcoder Beginner Contest 409
By pan_g
(Atcoder ID : GjyBilly)
To commemorate the thirty-seventh all do ABC.
A Conflict
判断一下，存在 $A_i = T_i = $ o 则是 Yes ，否则是 No 。
B Citation
写的最复杂的 B 题
先对 $A$ 进行排序，依次便利，倒序遍历 $A_i$ ，后面的所有都大于等于它，记该数量为 $x$ 。
然后对 $A_{i - 1}$ 到 $A_i$ 之间的数进行判断。
如果 $x \geq A_i$ ，则为 $A_i$ ；如果 $x \geq A_{i - 1}$ ，则为 $A_{i - 1}$ ；否则不在这个区间。
C Equilateral Triangle
首先可以发现，只有 $N$ 是 $3$ 的倍数时才存在等边三角形。
接着就是对于 $\mod \dfrac N 3$ 意义下相同的点，可以构成等边，贡献为三点上的点数乘积。
D String Rotation
首先，要求他只能操作一次，所以考虑让这次操作最优，由于要求字典序最小，所以小的要尽量靠前。
如果出现相邻的逆序对，说明可以将前者往后移，使得字典序变小，从前往后扫找到的一定最优。
接着，让这个较大的往后移，遇到第一个大于它的字典的字母的位置，我们就要放在该位置的前面，保证字典序尽量优，于是我们做完了。
时间复杂度 $O(N)$ 。
E Pair Annihilation
考虑贪心，因为正电荷往负电荷走，和负电荷往正电荷走，代价是一样的，所以直接考虑集聚到最近的根。
统计贡献即可，时间复杂度 $O(N)$ 。
F Connecting Points
脑子抽了，没想到优先队列
首先，因为 $N, Q$ 很小，所以可以暴力连边扔进一个优先队列里，用并查集维护连通性。
对于新加入的点，我们可以对先前的点连边，加入优先队列，加几个简单的判断就好了。
于是就很轻松的做完了，时间复杂度 $O((N + Q)^2\log (N + Q))$ 。
G Accumulation of Wealth
首先，考虑计算 $\geq 2$ 的 $k$ 在第 $i$ 次第一次出现的概率，那么就是 $(i - 1)$ 次出现 $(k - 2)$ 个数，然后在最后一次出现 $k$ ，也就是 $\begin{pmatrix} i - 1 \\ k - 2 \end{pmatrix}p ^ {k - 1}(1 - p) ^ {i - k + 1}$ 。
设 $f(x)$ 表示 $k$ 出现一次后，还有 $x$ 次操作的情况下， $k$ 出现的期望次数。
考虑当前期望次数为 $E$ ，那么下一次的期望次数为 $E + (1 - p)\dfrac EN$ ，其中 $N$ 是当前长度。
所以就有 $f(x) = f(x - 1)\dfrac{N - x + 1 - p}{N - x}$ 的递推式，可以快速算出 $f(x)$ 。
接着再考虑总体的期望 $E(k)$ ：
$$ \begin{aligned} E(k) &= \sum_{i = k - 1} ^ {N - 1} \begin{pmatrix} i - 1 \\ k - 2 \end{pmatrix}p ^ {k - 1}(1 - p) ^ {i - k + 1} f(N - i - 1) \\ &= \sum_{i = 0} ^ {N - k} \begin{pmatrix} i + k - 2 \\ k - 2 \end{pmatrix}p ^ {k - 1}(1 - p) ^ {i} f(N - k - i) \\ &= p ^ {k - 1}\sum_{i = 0} ^ {N - k} \dfrac{(i + k - 2)!}{i!(k - 2)!} (1 - p) ^ {i} f(N - k - i) \\ &= \dfrac {p ^ {k - 1}}{(k - 2)!}\sum_{i = 0} ^ {N - k} \dfrac{(1 - p) ^ {i}}{i!} (N - (N - k - i) - 2)! f(N - k - i) \\ \end{aligned} $$
所以就可以生成函数了，
令 $F(x) = \sum_{i = 0}^{N - 2} \dfrac{(1 - p) ^ {i}}{i!} x^i, G(x) = \sum_{i = 0}^{N - 2} (N - i - 2)! f(i) x^i$ 。
所以 $E(k) = \dfrac {p ^ {k - 1}}{(k - 2)!} [x ^ {N - k}] F(x)G(x)$ ，最后一共 $N$ 个数。
于是 $E(1) = N - \sum_{k = 2}^N E_k$ ，然后就结束了，时间复杂度为 $O(N \log N)$ 。
