摘要： QOJ5402 术树数 将所有的环插入线性基，包括边走两次形成的环。 然后线性基主元就是做 gcd。复杂度 \(O((n+q)\log^2 k)\)。 P15939 [JOI Final 2026] 传奇团子吃家 / Legendary Dango Eater 假设前面和为 \(s\)，扫到一个段符 阅读全文

摘要： https://www.luogu.com.cn/problem/P7342 贡献法，从对角线出发走到 \((0,n-1)\)，也就是从 \(F(x,y)=F(x,y)(\frac{1}{(1-x)(1-y)}-1)+1,F(x,y)=\frac{1-x-y+xy}{1-2(x+y-xy)}=(1- 阅读全文

摘要： https://atcoder.jp/contests/arc220 performance: 1824 A - Sum of Reciprocals of Squares \(n=x^2\) 可以构造 \(n\) 个 \(\frac{1}{x^2}\)。 \(\frac{1}{x^2}\) 可以变 阅读全文

摘要： https://cplusoj.com/d/master/contest/6a058a9cc3e1ba0889c35849 T1 早八（class） 类似猫树，一个区间的贡献挂在其跨过中点的线段树节点上。 那么只需要节点内关心上课的前后缀连续段，我们可以使用二维偏序计算没有贡献的权值和。 主席树维护 阅读全文

摘要： https://www.luogu.com.cn/problem/P14010 类似 IOI2012 理想城 缩行/列，变成 \(dis_1(u,v)+dis_2(u,v)\)。 T1 点分治，建出虚树，然后 T2 虚树点分治，统计合法路径数量，复杂度 \(O(n\log^2 n)\)，空间 \(O 阅读全文

摘要： https://www.luogu.com.cn/problem/CF936E 类似 IOI2012 理想城，将行/列缩点，所以变成求 \(\min_{x\in S} dis_1(u,x)+dis_2(u,x)\)。 cdq，只用处理到静态的点集最近距离。 对第二棵树点分治，距离转化为 \(dep_ 阅读全文

摘要： https://www.luogu.com.cn/problem/P6137 分别考虑 x 轴和 y 轴的贡献。 假设下面考虑 y 轴贡献，那么将每个连续的行缩成一个点，然后如果两行有公共点就连边。 这样连出一棵树，两点之间一定是走这个树边到达。所以计算 \(\sum s_i(n-s_i)\) 就好 阅读全文

摘要： https://www.luogu.com.cn/problem/P6132 人话：有标号根向森林，一个森林的系数为 \(k^{\mathrm{cntEdge}}\)，要求每个点入度在集合 \(S\) 内。\(S\subseteq\{0,1,2,3\}\)。 首先必须有 \(0\in S\)，否则一 阅读全文

摘要： https://www.luogu.com.cn/problem/P5850 GF：\(n![x^n]\prod_{i=1}^k (ix+1)\)。 重点考虑后面那个多项式如何求： \[\begin{aligned} F(x)&=\exp(\sum_{i=1}^k \ln(ix+1))\\ &=\e 阅读全文

摘要： https://www.luogu.com.cn/problem/CF1603D 代价：\(c(l,r)=\sum_{d=l}^{r} S_\varphi(\left\lfloor\frac{r}{d}\right\rfloor)\)。 代价满足四边形不等式。 注意到如果一个段满足 \(2l>r\) 阅读全文