标签：underset 2024.3 pmod 多项式 sum 3.15 求逆 端点

Sat

LGR-176（Div.2）

A. 区间和问题，一眼盯真：前缀和。
B. bfs，顺便记一下转移方向。
C. 最小化最大值，二分答案，用点 DS 实时维护逆序对即可，笔者用了线段树。
D. 区间DP，预处理一下 \(a_i^{a_j}\) 的值，然后记 \(f_{l,r,0/1}\) 表示到达了 \([l,r]\) 区间，并且最后一步是取了头部/尾部到达该状态，从 \(f_{1,n-1,1}\) 与 \(f_{2,n,0}\) 开始即可。
E. 先离散化，然后二分，双 \(\log\) 搞定（虽然正解单 \(\log\)）。
F. 首先改删边为加边，使用 \(\mathcal{O}(1)\) 求 LCA，并且用并查集合并，实时维护每个连通块当时的直径长度（multiset 等），两个端点，运用结论：合并两棵树的直径的端点一定是原两棵树的两条直径的四个端点中的两个。
G. 可以枚举（有点事没写，虽然也不太会）（为什么枚举复杂度对了啊？！）

Sun

作业题

【省选联考 2020 A 卷】

给定图 \(G\)，记 \(T\) 是 \(G\) 的一棵生成树，\(e\) 是 \(G\) 中的一条边，\(w(e)\) 表示 \(e\) 的边权，求：

\[\underset{T}{\sum} (\underset{e\in T}{\sum} w(e)) \times \underset{e\in T}{\gcd} \{w(e)\} \]

其中 \(|V|\leq 30, w(e)\leq 1.6\times 10^5\)。

---

欧拉反演，得到：

\[\overset{W}{\underset{d=1}{\sum}} \varphi(d) \underset{T}{\sum} \underset{e\in T\land d\mid w(e)}{\sum} w(e) \]

然后拉出权值是 \(d\) 的倍数的边，求所有生成树的边权和，这并不好处理，但是考虑多项式 \((w(e)x+1)\)，这可以使得乘法转加法，在 \(\pmod {x^2}\) 意义下进行多项式加减乘法和多项式求逆。

当然，考虑对于常数项为 \(0\) 的多项式，此时没有逆，直接用一次项进行消元。

附：多项式求逆（牛顿迭代式）：设已知 \(F\) 是 \(A\) 在 \(\pmod {x^{\lceil{\frac{n}{2}}\rceil}}\) 意义下的逆，要求 \(G\) 是 \(A\) 在 \(\pmod {x^n}\) 意义下的逆，有：\(G(x)=2F(x)-F^2(x)A(x)\)，在本题中次数较低，可以直接一次迭代搞定。

标签：underset,2024.3,pmod,多项式,sum,3.15,求逆,端点
From： https://www.cnblogs.com/ydzr00000/p/18063785