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)$ 。