Codeforces 86D - Powerful array
题目链接：Codeforces 86D
莫队算法模板题，渐进时间复杂度 \(O(n\sqrt{n})\)。
1 |
|
0%
计蒜客 41399 - Light bulbs
题目链接：ICPC 2019 上海网络赛B题
对区间 \([l,r]\) 离散化成四个点 \(l - 1\)、\(l\)、\(r-1\)、\(r\)，然后分块维护，渐进时间复杂度 \(O(T \times (4m \log 4m + 4m \sqrt{4m}))\)。
1 | #include <bits/stdc++.h> |
HDU 6534 - Chika and Friendly Pairs
题目链接：HDU 6534
考虑莫队算法，对 \(a_i\)、\(a_i + k\)、\(a_i - k\) 进行离散化，用树状数组维护一个值域的前缀和。渐进时间复杂度 \(O(n \times \sqrt{n} \times \log n)\)。
这里要注意我们对于每一个 \(a_i\)，要先预处理出 \(a_i - k\)、\(a_i\) 和 \(a_i + k\) 离散化之后的值，然后在 add 和 remove 操作的时候就可以 \(O(1)\) 得到它们离散化之后的结果，否则会TLE。
1 | #include <bits/stdc++.h> |
BZOJ 2038 - 小Z的袜子
题目链接：BZOJ 2038
莫队算法模板题，将原序列分成 \(\sqrt{n}\) 块，同一块内的询问按照右端点大小排序，离线询问，渐进时间复杂度 \(O(n \times \sqrt{n})\)。
1 | #include <bits/stdc++.h> |
Codeforce 1217E - Sum Queries
题目链接：Codeforce 1217E
首先我们考虑一个Balanced Multiset总和的每个位置可能存在两种情况：
- 总和\(s_i\)就是这个集合内某个数字\(x\)的第\(i\)位，除了\(x\)之外的其余数字的第\(i\)位均为\(0\)
- 总和\(s_i\)就是这个集合内某个数字\(x\)的第\(i\)位，但是不满足除了\(x\)之外的其余数字的第\(i\)位均为\(0\)，所以\(\sum x_i \bmod 10 = s_i\)，这种情况下一定会产生进位
- 经过分析可以知道第二种情况是不可能的，我们可以这样反证：如果第\(i\)位置是这种情况，第\(i+1\)位是会接受到第\(i\)位的进位，那么第\(i+1\)位就不可能是第一种情况，即第\(i+1\)位会产生进位，以此类推，最前面一位也会产生进位，假设这个进位的位置为\(p\)，这显然是不符合定义的，因为原集合当中\(p\)位置都是\(0\)，故不可能成立。
因此我们可以得到一个推论，任何一个Unbalanced Multiset，无论怎么添加元素，这个集合依旧是Unbalanced。那么我们要找一个和最小的Unbalanced Multiset，其实也就是找一个两个元素的集合，使得这两个元素不满足上述的第一类情况。简而言之，对于每个询问，我们需要找到一组\((a_i,a_j)\)，满足\(l \leq i < j \leq r\)，使得第一类Balanced条件被破坏，最小的\(a_i+a_j\)就是问题的答案。
考虑用线段树维护区间的一些信息。我们可以把一个十进制数按位置拆分，对于要维护的区间用一个长度为\(\lceil \log_{10} \max\{ a_i \} \rceil\)的数组来记录区间内的数中，那些不为\(0\)的位置被哪些数使用，这些数的最小值是多少。接着还需要一个变量来维护区间最小的\(a_i+a_j\)。在Push-Up操作的时候，第一个数组很好维护，我们考虑如何维护第二个量，这里记录为\(f_o\)，首先\(f \leq \min \{ f_l, f_r \}\)，\(f_o\)、\(f_l\)和\(f_r\)分别是线段树当前的根、左子树和右子树维护的\(a_i+a_j\)的值，这意味着在左半个区间选择两个或者在右半个区间选择两个，当然我们也可以在左区间选择一个，右区间选择一个，这个时候就要用我们维护的第一个量来更新第二个量，详见代码。
渐进时间复杂度\(O((n+m)\log n \times \lceil \log_{10} \max\{ a_i \} \rceil)\)。
1 | #include <bits/stdc++.h> |
Codeforces 1217D - Coloring Edges
题目链接：Codeforces 1217D
题目要求给出一种边的染色方案，使得所有的环上必须存在至少两种颜色，并且用的颜色数量最少。
在有向图上DFS的时候，每出现一个返祖边，就出现一个环，只要让返祖边的颜色与其他的边不一样即可，所以最多有两种颜色。我们可以在用栈维护当前DFS的链，然后寻找返祖边即可。
渐进时间复杂度 \(O(n + m)\)。
1 | #include <bits/stdc++.h> |
计蒜客41384 - so easy
题目链接：ICPC 2019 徐州赛区网络赛 B
所有的答案只可能是\(x_i\)和\(x_i + 1\)，对这些点离散化之后，使用并查集维护从当前点开始向右第一个合法位置，合并的时候向右合并即可。
渐进时间复杂度\(O(q \cdot \alpha(2n))\)。
1 | #include <bits/stdc++.h> |
计蒜客41387 - XKC's basketball team
题目链接：ICPC 2019 徐州赛区网络赛 E
对于每个\(a_i\)，我们要找一个最大的\(j > i\)，满足\(a_j \geq a_i + m\)。
考离线询问。对于一个点\(a_i\)，加入一个询问和一个修改——在\(i\)位置插入\(a_i\)，和一个查询——比\(a_i + m\)大的最大的\(j\)。我们可以对修改和查询进行排序，用优先队列维护比当前\(a_i + m\)大的最大的\(j\)，然后离线回答即可。
渐进时间复杂度\(O(n \log n)\)。
1 | #include <bits/stdc++.h> |
快速傅立叶变换（FFT）学习笔记
经典问题：记 \(f(x) = \sum_{i=0}^{n} a_i x^i\)，\(g(x) = \sum_{i=0}^{m} b_i x^i\)，其中\(1\leq n, m \leq 10^5\)，求\(f \cdot g (x)\)。
显然如果我们做朴素的多项式乘法，时间复杂度是 \(O(nm)\) 的。我们可以使用快速傅立叶变换（FFT）在 \(O(c \log c)\) 的时间内解决此问题，其中 \(c\) 是不小于 \(n+m\) 的最小的 \(2\) 的幂。
本文是笔者学习FFT的笔记和一些思考，不推荐作为教程食用。
在学习FFT之前，我们首先要理解一些概念。
多项式的系数表示和点值表示
对于多项式\(f(x) = \sum_{i=0}^{n} a_i x^i\)，把系数写成向量的形式\(\vec{a} = [a_0, a_1, \cdots, a_n]\)，则\(\vec{a}\)称为多项式的系数表示。我们输入一个\(x\)，对\(x\)求\(f(x)\)可以得到一个\(y\)，表示这个多项式函数在\(x\)点处的值。
我们知道，\(n+1\)个点可以唯一确定一个\(n\)次多项式，那么我们可以使用\(n+1\)个序偶对\((x_i, y_i)\)来表示这个多项式，这称为多项式的点值表示。如何从点值表示得到任意\(x\)处的函数值呢？可以使用拉格朗日差值法，由于与FFT关系不大，故这里不做具体说明。
离散傅立叶变换（DFT）与反变换（IDFT）
对于一个系数表示\(\vec{a} = [a_0, a_1, \cdots, a_n]\)，对其做离散傅立叶变换得到：
\[ {\rm DFT}(\vec{a}) = [f(w_{n}^{0}),f(w_{n}^{1}),f(w_{n}^{2})\cdots,f(w_{n}^{n-1})] \]
设其表示的多项式为\(\hat{f}(x)\)，我们可以对其做离散傅立叶变换的反变换重新的到\(f(x)\)，即向量\(\vec{a}\)：
\[ \vec{a} = {\rm IDFT} ({\rm DFT} (\vec{a})) = \frac{1}{n} [\hat{f}(w_{n}^{0}),\hat{f}(w_{n}^{-1}),\hat{f}(w_{n}^{-2})\cdots,\hat{f}(w_{n}^{-(n-1)})] \]
其中\(w_{n}^{k}\)为\(x^n = 1\)在复数域中的根，称为\(n\)次单位根，\(k=1\)的时候又称为本原单位根。
多项式乘法的原理
考虑\(n\)次的多项式\(f(x)\)和\(m\)次多项式相乘会产生一个\(n+m\)次的多项式，所以我们只需要获得两个多项式的\(n+m+1\)个点形成新的多项式的点值表示，这一点可以取\(n+m+1\)次单位根做\(\rm DFT\)，然后对得到的向量做\(\rm IDFT\)就可以得到目标多项式的系数表示了。即：
\[\vec{c} = {\rm IDFT} [{\rm DFT}(\vec{a}) \circ {\rm DFT}(\vec{b})] = \vec{a} * \vec{b}\]
这里也验证了傅立叶变换时域卷积等于频域乘积的性质。
快速求解DFT和IDFT的方法
我们知道卷积的求解和差值的求解都是\(O(n^2)\)的，和朴素的求法相比并没有提升，我么考虑用分治的方法来优化DFT。 考虑\(w_n\)与\(w_{2n}\)，有这样的两条性质：
\[ \left\{ \begin{aligned} & (w_{2n}^{k})^2 = w_{n}^{k} \\ & w_{2n}^{n+k} = -w_{2n}^{k} \end{aligned} \right . \]
这里可以在复平面上画图理解，当然《复变函数》中也有该性质的证明，这里不必过于纠结，会用即可。
设\(f(x) = \sum_{i=0}^{n} a_i x^i\)，\(n=2m\)，我们考虑将其项的次数按照奇偶进行分类：
\[ \begin{aligned} f(x) = & \sum_{i=0}^{n} a_i x^i \\ = & \sum_{i=0}^{m} a_{2i} x^{2i} + \sum_{i=0}^{m} a_{2i+1} x^{2i+1} \\ = & \sum_{i=0}^{m} a_{2i} x^{2i} + x \sum_{i=0}^{m} a_{2i+1} x^{2i} \\ = & f_0(x^2) + x f_1(x^2) \end{aligned} \]
假设\(0 \leq k < m\)，那么对于\(w_{n}^{k}\)：
\[\begin{aligned} f(w_{n}^{k}) = & f_0((w_{n}^{k})^2) + w_{n}^{k} f_1((w_{n}^{k})^2) \\ = & f_0(w_{m}^{k}) + w_{n}^{k} f_1(w_{m}^{k}) \end{aligned} \]
对于\(w_{n}^{m+k}\)：
\[ \begin{aligned} f(w_{n}^{m+k}) = & f_0((w_{n}^{m+k})^2) + w_{n}^{m+k} f_1((w_{n}^{m+k})^2) \\ = & f_0(w_{m}^{k}) - w_{n}^{k} f_1(w_{m}^{k}) \end{aligned} \]
因此就可以用分治的方法快速计算DFT了。
位逆序置换与非递归FFT
为了加速FFT的过程，我们可以将FFT写成非递归的形式，考虑展开递归树。
假设我们有8个数\([(0,1,2,3,4,5,6,7)]\)，经过一次递归之后变成\([(0,2,4,6), (1,3,5,7)]\)，经过第二次递归之后变成\([(0,4),(2,6),(1,5),(3,7)]\)，经过第三次递归之后变成\([(0), (4), (2), (6), (1), (5),(3),(7)]\)，我们发现第\(i\)位是\(i\)的二进制数翻转对应的那个十进制数字，因此我们可以把每个数字放在它最后的位置上，然后逐层向上还原，写成非递归版的FFT。
一份常数比较大的模板
洛谷上\(10^6\)级别的多项式乘法有两个点是TLE的，LOJ上\(10^5\)级别的多项式乘法通过没什么问题。（待后续更新）
1 | #include <bits/stdc++.h> |
计蒜客 41302 - K Sum
题目链接：ICPC 2019 南京网络赛 E 题
思路
\(f_n(k)\)化简得： \[ f_n(k) \begin{aligned} & = \sum_{u=1}^{n} \lfloor \frac{n}{u} \rfloor ^ k \sum_{d|u} d^2 \mu(\frac{u}{d}) \end{aligned} \] 代入目标式并交换求和次序： \[\begin{aligned} & \sum_{i=2}^{k} \sum_{u=1}^{n} \lfloor \frac{n}{u} \rfloor ^ k \sum_{d|u} d^2 \mu(\frac{u}{d}) \\ =& \sum_{u=1}^{n}\sum_{i=2}^{k} \lfloor \frac{n}{u} \rfloor ^ k \sum_{d|u} d^2 \mu(\frac{u}{d}) \\ =& \sum_{u=1}^{n} t(\lfloor \frac{n}{u} \rfloor) ({\rm Id}^2 * \mu)(u) \end{aligned} \] 其中\(t(\lfloor \frac{n}{u} \rfloor)\)表示一个等比数列求和的结果，对于比较大的 \(k\)，可以考虑欧拉函数降幂，然后可以整除分块求解。坑点是要特判公比为 \(1\) 的情况，公比为 \(1\) 的时候的 \(k\) 的计算值是 \(k \bmod P\) 而不是 \(k \bmod \varphi(P)\)。 下面考虑求式中 Direchlet 卷积的前缀和。\(n\)的范围是\(10^9\)，考虑使用亚线性筛。
记 \(f(x) =({\rm Id}^2 * \mu)(x)\)，\(g(x) = 1\)，则\(f * g = {\rm Id}^2 * \mu * 1 = {\rm Id}^2 * \epsilon = {\rm Id}^2\)，可求前缀和，考虑杜教筛。 设\(F(n) = \sum_{x=1}^{n} f(x)\)，则可以对\(f*g\)求和推得: \[ F(n) = \frac{n(n+1)(2n+1)}{6} - \sum_{d=2}^{n} F(\lfloor \frac{n}{d} \rfloor) \] 线性筛预处理\(n \leq 10^6\)，然后杜教筛即可。
渐进时间复杂度\(O(T (n^{\frac{2}{3}} + \sqrt{n} \times \log P) )\)。
代码
1 | #include <bits/stdc++.h> |