操作集锦  题目描述 给定一个长度为 的有小写字母组成的字符串。 求长度为 的本质不同的子序列个数，对 取模。 正解 如果设 为考虑到第 个位置，且第 个位置必须选，选出的本质不同的子序列个数。 设出状态不难，难的是转移如何不会重复。 如果一个子序列只在出现的第一次被算入答案，就不会计算重复了对吧。 考虑构造出序列自动机（位置为 ，字符 的下一个位置），这是找子序列第一次出现的常见套路。 那么转移就很简单了，当前位置为 ，枚举当前长度为 ，转移字符为 ，则有 的转移。 最后所有 就是答案了。  #include <bits/stdc++.h> #define N 1005 usin...

旗鼓相当的对手  题目描述 给定一个 个点的树，树有点权。 如果 为 和 的最近公共祖先(LCA)，并且 和 的树上距离等于 ，那么点 的答案就会加上 。 求所有点的答案。 正解 考虑暴力 dp，设 表示 的子树内离 的距离为 的点的个数，设 表示 的子树内离 的距离为 的点权和。 每次合并一颗子树，更新答案并且更新 dp 数组，时间复杂度 。 发现 dp 复杂度只跟深度有关，那么长链剖分后可以优化复杂度至 。 其实还有 dsu 的做法，每次暴力合并复杂度也没有问题，是 的。 这里给出长链剖分的代码 :  #include <bits/stdc++.h> #define N 100...

rt，直接 Splay 可以过 B