随笔

算[l, r]区间里所有子区间最小值的和。

对每个位置i向左知道第一个小于它的位置，向右找到第一个小于它的位置，算算贡献。

考虑可以用单调栈算。

但是如果一个区间里同一个最小值出现多次就挂了，所以考虑魔改一下，对于右边找到第一个小于它的点，对于左边找到第一个小于等于它的点并记录位置，这样的话就相当于只算了区间里第一次出现的点的贡献。

 stack[++top][1] = 1; stack[top][0] = 0;
    for (int i = 2; i <= l; i++)
    {
        while (top && height[i] < stack[top][0]) ri[stack[top--][1]] = i;
        le[i] = stack[top][1]; stack[++top][1] = i; stack[top][0] = height[i];
    }
    while (top) ri[stack[top--][1]] = l + 1;

SA插入特殊值的时候最好插1

给出数列\(f_1 \dots f_n\)

\(T\)组询问，每次给定\(n\)，\(m\)，求\(\sum_{i = 1}^{n} \sum_{j = 1}^{m} f_{gcd(i, j)}\)

令\(g = \mu \ast f\)

求\(g\)的方法

void get_g_3(int N, const int *f, int *g) {
  for (int i = 1; i <= N; i++) g[i] = f[i];
  for (int i = 0; i < prime_count; i++)
    for (int j = N / prime[i]; j >= 1; j--)
      g[j * prime[i]] = (g[j * prime[i]] - g[j]) % mod;
} // Magic! O(nloglogn)

群直积的卷积变换可以分解成独立的卷积变换

定义函数\(f_p(n)=n==p^k?f(n):0\)

所以积性函数\(f = f_2 \ast f_3 \ast f_5 \dots f_n\)

这是因为可以将积性函数\(f\)按质因子拆开，根据定义只有一种情况也就是\(n\)的每个质因子分别在对应的函数里的时候会对\(f\)的值产生贡献。

那么如何算这个群卷积呢？

考虑对于前\(n\)个可以变成前\(n - 1\)个的卷积和第\(n\)个的卷积卷起来。

发现只有在第\(n\)个函数传进去的参数是\(p ^ k\)的时候才会产生贡献，于是枚举转移即可。

令

定义乘法为狄利克雷卷积，那么有

这是因为

而所有\(f_p\)的卷积就对应于\(n\)的分解中每一项的积

或者更直接地，使用DGF，有

复杂度证明(重要)

假设算任意数列\(f\)和积性函数\(g\)的卷积，这样做的复杂度实际上是

对\(\left \lfloor \frac{n}{\left \lfloor \frac{n}{x} \right \rfloor} \right \rfloor = x\)求成立时的范围：

对于下取整我们一般将它拆开考虑，有

如果有上面那个结论，那么有

移项，得

和

第一个式子显然是恒成立的，那么第二个式子我们分开讨论，如果\(x > \sqrt{n}\)，那么有\(\left \lfloor \frac{n}{x} \right \rfloor = 1\)，并且又有\(\frac{n}{x} > 1\)，所以\(x > \sqrt{n}\)的时候是不成立的。

对于\(x \leqslant \sqrt{n}\)的情况，因为对于不同的\(x\)，\(\left \lfloor \frac{n}{x} \right \rfloor\)是不同的，又有\(\left \lfloor \frac{n}{x} \right \rfloor > \left \lfloor \frac{n}{x + 1} \right \rfloor\)，\(\left \lfloor \frac{n}{x + 1} \right \rfloor + 1> \frac{n}{x + 1}\)，所以有\(\left \lfloor \frac{n}{x} \right \rfloor \geqslant \left \lfloor \frac{n}{x + 1} \right \rfloor + 1\)，即\(\left \lfloor \frac{n}{x} \right \rfloor > \frac{n}{x + 1}\)。

那么为什么对于\(x \leqslant \sqrt{n}\)，\(\left \lfloor \frac{n}{x} \right \rfloor\)互不相同呢？

考虑如果\(\left \lfloor \frac{n}{x} \right \rfloor = \left \lfloor \frac{n}{x + 1} \right \rfloor = t\)，那么有\((x + 1) \times t \leqslant n\)，即\(t + x \times t \leqslant n\)，因为\(x \leqslant \sqrt{n}\)，所以\(t \geqslant \sqrt{n}\)，所以\(x + x \times t \leqslant n\)，即\(x \times (t + 1) \leqslant n\)，所以用\(t + 1\)替换掉\(t\)是没有问题的，这就和之前规定的\(\left \lfloor \frac{n}{x} \right \rfloor = t\)不符，所以\(\left \lfloor \frac{n}{x} \right \rfloor\)都是互不相同的。

在平面直角坐标系中，横坐标之差为\(w\)，纵坐标之差为\(h\)的两个点之间的连线上有\(gcd(w, h) - 1\)个点。

假设\((x, y)\)为直线上的点，当且仅当\(x \times \frac{h}{w}\)为整数。

也就是说，\(w | h * x\)，设\(x' = w / gcd(w, h)\)，\(y' = h / gcd(w, h)\)，则此时\(gcd(x', y') = 1\)，且\(w | h * x\)当且仅当\(x' | y' * x\)，由于\(gcd(x', y') = 1\)，故上式等价于\(x' | x\)，由于\(0 \leqslant x \leqslant w\)，且\(x' | w\)。

所以合法点数为

去掉两个端点，则有\(gcd(w, h) - 1\)个点。

一个字符串的\(border\)可以分成\(log(|S|)\)组，每组为\(AB^k\)的形式，按长度\(> \frac{i}{2}\)和不大于来分。