BZOJ-3509. [CodeChef] COUNTARI

给定一个长度为 n ~(1 \leq n \leq 10^5) 的数组 a_i~(0 \leq a_i \leq 3\cdot 10^4),问有多少对 (i, j, k) 满足 i < j < ka_i - a_j = a_j - a_k

也就是统计有多少对长度为 3 的等差子序列(题目连接 BZOJ-3509, CodeChef COUNTARI

例如 3 5 3 6 3 4 10 4 5 2,就有 (1, 3, 5), (1, 6, 9), (1, 8, 9), (3, 6, 9), (3, 8, 9), (5, 6, 9), (5, 8, 9), (4, 6, 10), (4, 8, 10) 一共 9 对

假设现在枚举 j,就变成要寻找有多少对 (i, k) 满足 2a_j=a_i+a_k,如果不考虑 i < j < k 这个限制,也就是说 a_ia_k 可以随便在数组中选两个,并且加起来要是 2a_j

直接一个个去算 j 的话再枚举 (i, k) 复杂度十分高,大概是 \mathcal O(n^3),肯定是不能做到。但是回头想想,现在要做的操作是从 a 中取出一个数,再从 a 中取出一个数,组合起来。这会想到母函数或者多项式乘法,因为多项式乘法的结果就是从每个多项式中取出一项,组合起来(指数相加)

所以现在可以构造 a 的母函数(如果不太清楚的可以先做这题

A(x) = x^2+3x^3+2x^4+2x^5+x^6+x^{10}

那么将 A(x) 平方后就可以得到要求的答案,2a_j 那一项的系数就是 (i, k) 的方案数,至于多项式乘法,只要用 FFT 优化就好了,关于 FFT 可以看这里

然后现在来考虑存在 i < j < k 这个限制的情况,还是可以枚举 j,然后计算 (i, k),你同样可以构造出母函数,只不过这回要构造两个母函数,一个表示 j 左边的序列,一个表示 j 右边的序列,因为要求从左右两边选出 (i, k)。例如说 j = 4, a_j = 6,它左边序列的母函数就是 L(x) = 2x^3+x^5,右边序列的母函数是 R(x)=x^2+x^3+2x^4+x^5+x^{10},然后求出 L(x)R(x)2a_j 项的系数就是答案,但是这样还不如暴力,因为你要求 n 次 FFT,复杂度 \mathcal O(n^2\log n)

但是这样是可以优化的,因为一次 FFT 只求一个点的值太浪费了,我们可以一次性求出一段区间的值,然后对于在区间内的 (i, j, k) 暴力求解,也就是对于区间 [L, R],用 FFT 求出满足 i < L, L \leq j \leq R, R < k 的方案数,再暴力求出区间内的方案数,如果设块的大小是 \mathcal O(\sqrt{n\log n}),最终复杂度大约会是 \mathcal O(n\sqrt{n\log n})

 

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/04/bzoj-3509

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.