76.CF1967 Codeforces Round 942 (Div. 1)
CF1967A
CF1967B1
\[b\times \gcd(a,b)|a+b \to qi^2|(p+q)i \to qi|(p+q)\to q|p \to b|a \]反过来也能推到。
CF1967B2
\[a+b|b\times \gcd(a,b) \to (p+q)i|qi^2\to (p+q)|qi \to (p+q)|i \]枚举 \(p,q\)，因为 \(p<i,pi< n\)，所以 \(p^2< \sqrt n\)，\(q\) 同理。
容易做。
CF1967C
一个树状数组的结构。
相当于 \(k\) 次前缀和下的组合系数。
用树状数组模拟求出 \(a_1\cdots a_{i-1}\)，乘上对应系数可以求出 \(a_i\)。
CF1967D
CF1967E1
经典双直线 \(\mathcal O(n\sqrt n)\)。
77.CF1965
78.CF1969
CF1969E
记录每个点上的数前一个出现和后一个出现的位置。
合法区间是 \(n\) 个二维矩阵。
扫描线求出 \(l_i\) 表示以 \(i\) 为右端点，最大的不合法左端点。
按照 \(l_i\) 排序，最大的 \(l_i\) 一定要修改（必要性），记已经修改过的 \(\min(l_i)\) 为 \(mn\)，若之后的 \(l_i\)，有 \(i\ge mn\)，则跳过，一定最优。
79.CF335E
考虑知道 \(B\) 求 \(A\)。
对于一个高度为 \(i\) 的楼房，概率为 \(\frac{1}{2^i}\)，高度 \(\ge i\) 的概率为 \(\frac{1}{2^{i-1}}\)，小于的概率即为 \(1-\frac{1}{2^{i-1}}\)。
考虑从一栋楼的第 \(i\) 层出发的通道的期望长度（除去最左点），则有：
\[p\sum_{k=0}^{+\infty}(1-p)^k(k+1)=\frac{1}{p}=2^{i-1} \]得到对于 \(B\) 的贡献也是 \(2^{i-1}\)，所以 \(A=B\)。
注意，这里只能推出 \(B\) 走第 \(i\) 层的通道对 \(A\) 的贡献。
再考虑知 \(A\) 求 \(B\)。
这里就不同了，因为 \(A\) 对每一层不同的分配数量对 \(B\) 的贡献都有一个不同系数。
考虑从低往上考虑，不断将最大值限制提高。
设当前高度为 \(x\)，长度为 \(j\)，则有：
\[(n-j)P(\ge x)^2P(<x)^{j-1}(2^{i-1}-2^{i-2}(1+\sum_{k=0}^{j-1}\frac{k\cdot P(=x)^k}{P(<x)^k})) \]再加上高度为 \(1\) 的 \(n\)。
时间复杂度 \(\mathcal O(nm)\)，好像可以矩阵优化。
标签：系数,frac,记录,高度,ge,qi,考虑 From： https://www.cnblogs.com/orzz/p/18174804