YZOJ P3752 序列求差问题

时间限制：2000MS      内存限制：131072KB

出题人：Night        难度：\(6.0\)

• 题目描述

有一个序列 \(x_1,x_2,\cdots,x_n\) 。

求有多少个从 \(1,2,\cdots,n\) 中取三个元素的排列 \((a,b,c)\) 满足 \(x_a=x_b-x_c\) 。

由于是排列，所以 \((a,b,c)\) 与 \((c,b,a)\) 视为两组解。

• 输入格式

第一行一个整数 \(n\) 表示序列长度。

第二行为 \(n\) 个整数表示序列里的 \(n\) 个数。

• 输出格式

一行一个正整数，表示答案。

• 样例输入

• 样例输出

• 数据规模与约定

对于 \(20\%\) 的数据，\(1 \leq n \leq 500\)；

对于 \(45\%\) 的数据，\(1 \leq n \leq 5000\)；

对于 \(100\%\) 的数据，\(1 \leq n \leq 1000000\)，\(0 \leq \left|x_i\right| \leq 100000\) 。

 

 

 

---

 

 

 

首先这个东西和 \(x_a+x_b=x_c\) 是等价的。

对于 \(n \leq 500\) 的数据，显然可以 \(O(n^3)\) 枚举 \((a,b,c)\) 暴力判断。

对于 \(n \leq 5000\) 的数据，可以记桶 \(cnt_i\) 表示 \(i=x_j\) 的不同 \(j\) 的个数，只要枚举 \((a,b)\) ，答案加上 \(cnt_{x_a+x_b}\) 即可，\(O(n^2)\)。

然后对于 \(100\%\) 的数据，出题人就发现 \(x_a+x_b=x_c\) 这个东西很像多项式乘法，因为可以把 \(cnt_{x_a}\) 和 \(cnt_{x_b}\) 贡献到 \(cnt_{x_c}\) 上。

所以就把 \(cnt\) 作为一个多项式，与它自己相乘，得到的就是答案了。

多项式乘法用 FFT 优化至 \(O(nlogn)\) 。

细节：

1，因为不能取两个相同的，所以 \(ans_{x_i+x_i}\) 要减一。

2，还有要特判一下 \(0\) 的情况，所以答案要减去 \(2 \times m \times (n-1)\) （其中 \(m\) 为 \(x\) 中 \(0\) 的个数）。

3，有负数，所以要整体偏移，\(x_a+diff+x_b+diff=x_c+2 \times diff\) ，注意多项式乘法的答案意义也有所变化。

4，因为答案可能超出 \(int\) ，所以不能使用 FWT/NTT 求解，而且 double 会被卡精度，所以要换成 long double 继续，正确的做法是考虑到答案肯定不超过 \(A^3_{1000000}=999997000002000000\)，可以使用 \(998244353\) 和 \(1004535809\) 两个模数分别 FNT 求一遍，然后再 CRT（中国剩余定理） 合并计算结果。

答案为 \(\sum ans_{x_i+2 \times diff}-2 \times m \times (n-1)\) 。