【FFT】Triple Sums_综合

分析：

如果不考虑取值相同，本题就非常简单了，直接用 $A_x$ 表示为值为 $x$ 的数量，然后求 $A^3$ 即可。
现在要考虑取值相同，很显然，如果是两个值取值相同的情况，这种情况会出现3次，如果是三个值都相同的情况，则会出现一次。所以，首先求 $A^3$ ，

再设一个多项式B，其中 $B_x$ 表示 $\frac x 2$ 出现的次数。
求出 $A\times B$

最后设一个多项式C，其中 $C_x$ 表示 $\frac x 3$ 出现的次数
求出C

答案就是 $\frac {A^3-A\times B\times 2-C} 6$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 100010
#define MOD 1004535809
typedef long long ll;
const int G=3;
const int siz=131072;
using namespace std;
ll fsp(ll x,int y){ll res=1;while(y){if(y&1)res=(res*x)%MOD;x=(x*x)%MOD;y>>=1;}return res;
}
void ntt(ll a[],int N,int flag){int i,j,k;for(i=1,j=0;i<N;i++){for(int d=N;j^=d>>=1,~j&d;);if(i<j)swap(a[i],a[j]);}for(i=1;i<N;i<<=1){ll wn=fsp(G,(MOD-1ll)/(2ll*i));if(flag==0)wn=fsp(wn,MOD-2);for(j=0;j<N;j+=i<<1){ll w=1;for(k=0;k<i;k++,w=(w*wn)%MOD){ll x=a[k+j],y=(a[i+j+k]*w)%MOD;a[j+k]=(x+y)%MOD;a[i+j+k]=(x-y+MOD)%MOD;}}}if(flag==0){ll inv=fsp(N,MOD-2);for(int i=0;i<N;i++)a[i]=(a[i]*inv)%MOD;}
}
ll A[500000],B[500000],C[500000];
int n,t[100000];
int main(){SF("%d",&n);for(int i=0;i<n;i++){SF("%d",&t[i]);t[i]+=20000;A[t[i]]++;B[t[i]*2]++;C[t[i]*3]++;}ntt(A,siz,1);ntt(B,siz,1);for(int i=0;i<=siz;i++){A[i]=A[i]*((A[i]*A[i]%MOD-3ll*B[i]%MOD+MOD)%MOD)%MOD;}ntt(A,siz,0);ll inv6=fsp(6,MOD-2);for(int i=0;i<=siz;i++){A[i]=((A[i]+2ll*C[i])%MOD*inv6)%MOD;if(A[i]>0)PF("%d : %lld\n",i-60000,A[i]);}
}