做题笔记16

9.24

P8331 [ZJOI2022] 简单题

幽默题

这张图肯定是若干个杏仁拼在一起，证明？随便拿一个杏仁出来，如果我们加边，要么会有一个 \(K_4\) 同胚，要么会有至少一组平行的环，要么仍然是一个杏仁，前面两种情况容易分讨出来都是不合法的，这里就不写了

由于我们要求 \(S\) 到 \(T\) 的简单路径和，考虑建圆方树，这条路径会穿过多个杏仁，每个杏仁上有两个点需要被考虑，除了在 LCA 处的两个点肯定都是树上一对爷爷和孙子，如果我们能预处理出来每一对爷爷和孙子的原点的贡献就可以快速算了，可以维护一个二元组

现在考虑怎么快速算杏仁中两个点的贡献，只需要分讨两个点是否在同一条链上，设这个杏仁的两个端点是 \(A,B\)，杏仁中每个点和 \(A\) 的距离为 \(da\)，和 \(B\) 的距离为 \(db\)，不妨假设 \(da_{S}<da_{T}\)，记 \(C\) 为这个杏仁上的链数，\(V\) 为这个链上所有边的权值和，分类讨论：

• 当 \(S\) 和 \(T\) 在一条链上，二元组为 \(\left(C,V+(C-2)(da_{S}+db_{T})\right)\)
• 当 \(S\) 和 \(T\) 不在一条链上，二元组为 \(\left(2(C-1),2V+(C-3)(da_{S}+db_{T})\right)\)

这样两点的贡献可以 \(\mathcal{O}(1)\) 算了，理论复杂度可以线性，瓶颈在于求 LCA

P12536 [XJTUPC 2025] 我永远喜欢希儿·芙乐艾

这都被出烂了。

换根没用，本质就是子树和

对 \(A\) 分块，预处理一个系数数组，整块好处理，散块会有 \(nB\) 次链加和 \(B\) 次子树查，发现链加字数和可以看作一个 \(kdep_u+b\) 的形式，维护一下系数做单点修区间查就行了，复杂度 \(\mathcal{O}(n\sqrt{n})\)

AT_wtf19_c1 Triangular Lamps Easy

我们发现可以从一个点出发到达他下面的所有行，使得只有他下面的行里有亮的，那么可以说明，如果我们把所有最后亮着的灯推到同一行，再把初始的点也推到那一行，如果这一行的两个亮灯的状态相同，这个初始点就是合法的，现在再观察一下把每个点推下去，亮灯的状态，考虑点 \((0,0)\)，记每个点的亮灯状态为 \(t_{x,y}\)，我们可以递推得到 \(t_{x,y}=t_{x,y-1}\oplus t_{x-1,y-1}\)，这就是一个组合数的形式，那么亮灯当且仅当 \(x\subseteq y\)，对于不是 \((0,0)\) 的位置，只需要考虑其坐标的差值

我们在初始点 \((x,0)\)，发现 \(y\) 是不变的，而亮灯的充要是 \(\Delta x\subseteq y\)，由于保证有解，我们任意取一行判断都是可以的，我们不妨取 \(y=-2^{60}+1\) 那一条线，这条线上从 \(x\) 开始往后都是亮的，于是可以考虑二分，每次判断所有最终状态下亮着的点的推过去，在 \((x,-2^{60}+1)\) 处是不是还亮着的，判断一下奇偶性即可

AT_arc141_d [ARC141D] Non-divisible Set

我擦。

考虑到 \(2m\) 这个东西，我们可以把每个数拆成 \(k2^p\) 的形式，其中 \(k\) 是奇数，那么每一组 \(k\) 只能选而且必须选一个，接着考虑 \(k\) 之间有倍数关系的，若 \(c|d\)，那么 \(c2^{x}\) 和 \(d2^{y}\) 必须满足 \(x>y\)，那对于每一个 \(k\)，其合法的必然是一段区间，记为 \([l_k,r_k]\)，需满足 \(\forall k|k_1,l_k>l_{k_1},r_{k}<r_{k_1}\)，可以调和级数求解 \(l\) 和 \(r\)，复杂度线性对数

#6713. 「EC Final 2019」狄利克雷 k 次根 加强版

学习了迪克生成函数。

先取 ln 再 exp，关键是 DGF 的 ln 和 exp 怎么算

我们得知道怎么算导数和积分，有

\[\frac{\mathrm{d}\left(\frac{f_n}{n^x}\right)}{\mathrm{d}x}=-\ln n\frac{f_n}{n^x} \]

\[\int\frac{f_n}{n^x}\mathrm{d}x=-\frac{1}{\ln n}\frac{f_n}{n^x}+C \]

而我们不用真的去算 \(\ln n\)，反正最后会被消掉，我们可以直接取 \(\ln n\) 为 \(n\) 的质因子次数之和

那 ln 就是：

\[\ln F=\int \frac{F'}{F}\mathrm{d}x \]

exp：

\[\begin{aligned} e^{F}=G\\G'=F'e^{F}=F'G\\g_n \ln n=\sum_{d|n}g_{\frac{n}{d}}f_d\ln d \end{aligned} \]

CF1738G Anti-Increasing Addicts

牛。

补习了序理论。

首先最长链等于最小反链覆盖，所以我们必须要用 \(\le k-1\) 个反链覆盖所有最后选择留下来的点，\(k-1\) 条反链最多覆盖 \(n^2-(n-k+1)^2\) 个位置，因为第一条最多覆盖 \(2n-1\) 个，第二条最多覆盖 \(2n-3\) 个，以此类推，所以题目的限制已经是最严格的了

记 \(f_{x,y}\) 为从 \((x,y)\) 开始，只经过必须保留的点，最长链长度，那么存在 \(f_{x,y}=k\) 的时候必然无解，如果我们根据 \(f_{x,y}\) 的值分层，值相同的位置必定不存在偏序关系，为了最大化覆盖的位置，我们不妨令第 \(i\) 条反链从 \((n,i)\) 走到 \((i,n)\)，并且把所有没被覆盖过的 \(f\) 值为 \(k-i\) 的位置都覆盖了，这样如果所有的反链都不相交，我们就能覆盖 \(n^2-(n-k+1)^2\) 个位置

经典的，我们考虑贪心地往上走，也就是说，如果上面已经被覆盖了，或者再往上走就无法覆盖到某个 \(f\) 值为 \(k-i\) 的位置，这时候就该向右走了，具体的，我们记 \(lim_{v,y}\) 为第 \(y+1\) 列及以后，\(f\) 值为 \(v\) 的最大行，如果当前 \(lim_{k-i,y}=x\)，那么我们不会再往右走了

只要每条反链都能取满，我们就肯定能构造出来最优方案，也就是需要证明在上述贪心策略下，第 \(i\) 条反链必定经过 \((n-k+i,i)\) 和 \((i,n-k+1)\)

对于第 \(i\) 条反链，第 \(i+1\) 列及右边不会出现行数 \(>n-k+i\) 的 \(f\) 值为 \(k-i\) 的位置 \((x,y)\)，如果存在，那么有 \(x>n-k+i\)，这时候，其链末端行数 \(x'\) 有 \(x'\ge x+(k-i)>n\)，爆了

求 \(f\) 是简单的，总复杂度 \(\mathcal{O}(n^2)\)

9.25