YZOJ P3752 序列求差问题

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

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注