主要思路
看完题面就知道应该又是传统的字符串重工题，最后写了我 6.3KB。
首先建出 SAM 然后处理倍增+线段树维护 endpos 集合是显然需要的。然后开始考虑这个二元组的含义。
想了一段时间如何正着算，发现这个东西成立的条件是或，所以正着算只能用子集容斥。所以我们考虑把条件进行反转，变成强与形式，然后用所有的二元组的数量 \( {n – 1 \choose 2} \) 来减掉即可。
如何算正好不符合条件的二元组数量呢？分两种情况讨论：
- 最左区间和最右区间相交
- 最左区间和最右区间不相交
看完题面就知道应该又是传统的字符串重工题，最后写了我 6.3KB。
首先建出 SAM 然后处理倍增+线段树维护 endpos 集合是显然需要的。然后开始考虑这个二元组的含义。
想了一段时间如何正着算，发现这个东西成立的条件是或，所以正着算只能用子集容斥。所以我们考虑把条件进行反转，变成强与形式，然后用所有的二元组的数量 \( {n – 1 \choose 2} \) 来减掉即可。
如何算正好不符合条件的二元组数量呢？分两种情况讨论：
宏观很难看出什么东西，所以我们可以考虑每条边单独的贡献。
首先这个图是个仙人掌，所以我们需要分开考虑环边的贡献和树边的贡献。树边的贡献很好考虑，直接 \((2^{siz_u} – 1) \times (2^{siz_v} – 1)\) 即可。如果是环边就有点麻烦，我们需要枚举做贡献的最小弧长，然后再从某一个点作起点算两两出边大小乘积的答案。用前缀和优化可以省掉一维的转移复杂度。
Continue reading →一开始想了一个假的，后面写完了之后才意识到哪里错了，就很傻逼。
首先贪心的知道，肯定是第 \(i\) 小的数位于 \(K + i – 1\) 的位置上。我们算答案的时候会发现无非就是把贡献根据绝对值的拆法进行分开处理，一部分是 \((a_i – rk_i) – (k – 1)\)，还有一部分是 \((k – 1) – (a_i – rk_i)\)。所以我们需要一个数据结构来拆分这两个部分。
首先我们知道这两个部分肯定是连续的两段，因为前后的 Delta 都至多为 \(1\)。知道这个性质之后，我们其实可以尝试用主席树来搞区间内的段。考虑用势能线段树的那一套，我们可以把段一直下传，直到段完整为止。
对于完整的段，发现其实就是给上面那个贡献式子套 \(\sum\)，而且发现套 \(\sum\) 的时候要记录这一段和的左端点，这样就可以用等差数列直接搞了。
Continue reading →其实稍稍看一下，会发现 \([j|i][(j + k)|i]\) 满足的时候 \(k\) 并没有什么特别的限制，所以可以直接理解为选两个因数，然后就转化为了：
\[ \begin{aligned} & \sum_{i = 1}^n {\sigma_0(i) \choose 2} \\ =& \sum_{i = 1}^n \frac{\sigma_0^2(i) – \sigma_0(i)}{2}\end{aligned} \]
后面的那个 \(\sum \sigma_0(x)\) 可以直接数论分块，前面那个用 min_25 筛一下就好。有 \(f(p^k) = \prod (1 + c_i)^2\)。
Continue reading →