I. [ARC152C] Pivot
神仙题。
II. CF1792E Divisors and Table
III. CF1763D Valid Bitonic Permutations
IV. P6736 「Wdsr-2」白泽教育
注意到 \(n\in \{1,2,3\}\)。
- \(n=1\)：
即 \(a\uparrow^1 x=a^x\equiv b\pmod p\)，这是一个平凡的 BSGS 问题。
- \(n=2\)：
我们有
\[a\uparrow^2 x=\underbrace{a^{a^{a^{.^{.^{.^{a}}}}}}}_{x} \]根据 CF906D 的经典结论，当 \(x\ge r=\Theta(\log p)\) 时幂塔在模 \(p\) 意义下结果不变，所以直接做就可以了。
- \(n=3\)：
我们有
\[a\uparrow^3 x=\left. \underbrace{a^{a^{a^{.^{.^{.^{a}}}}}}}_{ \underbrace{a^{a^{a^{.^{.^{.^{a}}}}}}}_{ \underbrace{\vdots}_{a} } } \right\} b \]同 \(n=2\) 的情况，迭代次数最多只会是 \(4\)，直接做就好了。
V. P9405 [POI 2020/2021 R3] 星间旅行
神仙题。
VI. P5598 【XR-4】混乱度
神仙题。
VII. P3705 [SDOI2017] 新生舞会
显然的 0/1 分数优化，二分答案后直接跑费用流即可。我也不知道为什么能过。
VIII. P5516 [MtOI2019] 小铃的烦恼
神仙题。
IX. P3830 [SHOI2012] 随机树
神仙题。
X. CF1830C Hyperregular Bracket Strings
很厉害的题。
XI. UVA10652 Board Wrapping
凸包板子题。只需要知道向量旋转的结论就可以了。
XII. CF1967B2 Reverse Card (Hard Version)
尺子姐姐！/se
不妨套路地设 \(\gcd(a,b)=g\)，\(a=gx\)，\(b=gy\)。
引理
\[x^2\lt n,y^2\lt m \]证明
题目条件化为 \(x+y\mid gy\)。由于 \(\gcd(x+y,y)=\gcd(x,y)=1\)，所以 \(x+y\mid g\)。
注意到 \(x+y\lt g\)，而 \(g=\dfrac{a}{x}\le \dfrac{n}{x}\)，即得 \(x^2\lt n\)。\(y\) 的讨论是对称的。
注意到引理，我们直接枚举互素数对 \((x,y)\)，由于 \(a=gx\le n\)，\(b=gy\le m\)，所以 \(g\le \min\left(\dfrac{n}{x},\dfrac{m}{y}\right)\)；又 \(x+y\mid g\)，所以除以 \(x+y\) 后下取整即可。
时间复杂度 \(\Theta(n+m)\)。
XIII. P6835 [Cnoi2020] 线形生物
神题，可以加深对数学期望的了解。
XIV. CF1967C Fenwick Tree
尺子姐姐！！/se
注意到树高最多为 \(\Theta(\log n)\)，不难想到维护每一个 \(i\) 对其祖先的贡献。
发现做 \(k\) 次 Fenwick Sum，对应链上的深度差为 \(d\) 的节点中，儿子对祖先的贡献为 \(\displaystyle{d+k-1\choose k-1}\)。直接减去即可。
时间复杂度 \(\Theta(n\log n)\)。
XV. CF113D Museum
设 \(f(i,j)\) 为 A 在 \(i\)，B 在 \(j\) 的期望次数。由于终态 \((i,i)\) 只会出现 \(\{0,1\}\) 次，所以这里期望等于概率。
我们有显然的转移方程：
\[\begin{aligned} f(y,w)&\gets\sum_{(x,y)\in E}\sum_{(z,w)\in E} \frac{(1-p_x)(1-p_z)}{\deg_x\cdot\deg_z}f(x,z) \quad \\ &+\sum_{(z,w)\in E} \frac{p_y(1-p_z)}{\deg_z}f(y,z) \quad \\ &+ \sum_{(x,y)\in E}\frac{(1-p_x)p_w}{\deg_x }f(x,w) \quad \\ &+p_yp_w\cdot f(y,w) \end{aligned} \]额外地，如果 \((y,w)\) 是起点，那么 \(f(y,w)\) 的期望值还需要额外加 \(1\)，理由显然。
时间复杂度 \(\Theta(n^6)\)。代入 \(n=22\) 得到 \(1.13\times 10^8\)，精细实现应该是可以过的。
XVI. P3599 Koishi Loves Construction
见非传统题做题记录 Ett。
标签：le,记录,underbrace,sum,lt,数学,dfrac,Theta,部分 From： https://www.cnblogs.com/Starrykiller/p/18214360/math-problems