一些经典问题

DDDDD 问题

给一个正整数 $N$ 和 一个正个位数 $D$，求至少多少个 $D$ 组成的 $\overline{DD\dots DD}$ 可以被 $N$ 整除。

$1\le N\le 2\times 10^9$。

显然 $\overline{DD\dots DD}$ 可以表示为 $\frac{D\times(10^k-1)}{9}$，推一波式子：

$N\mid\frac{D\times(10^k-1)}{9}\\ 9N\mid D\times (10^k-1)\\ 设\,d=\gcd(D,9N):\\ \frac{9N}{d}\mid10^k-1\\ 10^k\equiv1\pmod{\frac{9N}{d}}$

此时，若 $10$ 和 $\frac{9N}{d}$ 不互质那么无解。

考虑如何求出 $k$ 的最小值，即答案，根据欧拉定理，有：

$10^{\varphi(\frac{9N}{d})}\equiv 1\pmod{\frac{9N}{d}}$

此时最小的 $k$ 一定是 $\varphi(\frac{9N}{d})$ 的因子.

那么枚举 $\varphi(\frac{9N}{d})$ 的因子，快速幂判断即可。

树的带权拓扑序问题

给定一棵有根树，每个点有个权值 $a_i$，对于该树的所有拓扑序 $p$，求 $\sum a_ip_i$ 的最大值。

设 $a$ 的最小值为 $a_u$，那么不难发现一定有 $p_u=p_{fa_u}+1$。

那么不妨把 $u$ 和 $fa_u$ 缩起来，给答案增加 $a_u$。

对于两个连通块 $x,y$，设其点数和 $a_i$ 总和为 $(siz_x,sm_x)$ 和 $(siz_y,sm_y)$，那么 $x$ 在 $y$ 前贡献为 $siz_x\times sm_y$，$y$ 在 $x$ 前贡献为 $siz_y\times sm_x$，所以 $x$ 排在 $y$ 前当且仅当 $siz_x\times sm_y\ge siz_y\times sm_x$ 即 $\frac{sm_x}{siz_x}\ge\frac{sm_y}{siz_y}$。

那么把连通块权值当成 $\frac{sm}{siz}$ 看作正常点即可。

合并 $u$ 的连通块 $(siz_u,sm_u)$ 和 $fa_u$ 的连通块 $(siz_{fa_u},sm_{fa_u})$ 会给答案增加 $siz_{fa_u}\times sm_u$，边合并边计算即可。

使用堆维护，时间复杂度 $O(n\log n)$。

区间虚树大小问题

给定一棵有点权的有根树和一个节点序列 $a$，$q$ 次询问，每次求 $a_{[l,r]}$ 到根的路径覆盖到的所有点的点权和。

可以离线。

可以回滚莫队维护，$O(n\sqrt n)$。

也可以先树剖再启发式合并维护每个点子树中点在 $a$ 中出现位置的集合，先把 $u$ 的贡献算进其重儿子，启发式合并维护轻儿子的贡献。

具体的，令 $u$ 的子树大小为子树中每个点在 $a$ 中出现的次数之和，按照这个定义进行重链剖分。

剖分完令 $w_u$ 为 $u$ 到其所在重链链顶的点权和，$st_u$ 为 $u$ 子树中每个点在 $a$ 中出现位置的集合，则 $st_u$ 直接从 $st_{hev_u}$ 继承（$hev_u$ 为 $u$ 的重儿子），然后把 $u$ 在 $a$ 中的出现位置插入到 $st_u$，再遍历 $u$ 的轻儿子 $v$，把 $x\in st_v$ 插入到 $st_u$。

每次插入 $x$ 找到其前驱后继 $lb,rb$，给 $l\in [lb,x],r\in [x,rb]$ 的所有区间 $[l,r]$ 增加 $w_u$ 的贡献，这个可以离线再用扫描线维护。

这样由于轻儿子 $st_v$ 的大小总是不超过 $st_u$ 的大小，所以时间复杂度是启发式合并的复杂度，总复杂度 $O(n\log ^2n)$。

参考：【2024NOI模拟赛11】项链 做题记录