云斗八月银组做题记录

比赛

C. 大鱼吃小鱼

区间或和区间最大值都可以用 st 表维护，然后倍增。
或者分块也可以。

D. 权值与下标

看见这个东西很容易想到拆贡献，拆因子。但是考虑到拆下标因子最大的会到 \(\displaystyle n ^ {\frac{m}{2}}\)。
我们遇见这样的东西，我们可以发现不同数的个数小于 $ n ^{\frac{1}{m}} $，所以我们可以直接枚举每次拿哪一个数，计数一下就好了。

E. 小Z的旅行路线

边权是 1 的图上的路径计数（路径长度是 k 的路径条数）可以使用邻接矩阵存图，然后矩阵快速幂。
当边权更大时，我们可以拆点，拆出来边权个点。