[BZOJ3771] Triple

Description

Let’s tell a sad story. Once upon a time, there was a poor woodcutter cutting firewood beside the river. Then a water God appeared in the river, took his axe and said, “Is this your axe?” The woodcutter looked at him, “yes, yes!” The water God threw the axe aside, and picked up one thing and asked, “this axe,Is it yours? ” The woodcutter could not see clearly, but he was afraid that he was really his axe, so he replied, “yes, yes!” The God of water threw aside the thing on his hand, took the third thing and asked, “Is this your axe?” The woodcutter could not see clearly, but he felt that if he went on like that he would not be able to cut wood.. So he answered again, “yes, yes! It really is! ” The water god looked at him and laughed. “Look at the way you look, it’s ugly!” And then disappeared. The woodcutter felt very pit father. He not only chop wood today, but also lost an axe to the water god. So he was going home to change his axe.. After returning home, he found that the real pit father had just begun. The water god was holding his axe. But it wasn’t necessarily the one he took out, or maybe the God of water didn’t know how to steal it from his house. In other words, the water God may have taken one of his, two or three axes. The woodcutter felt thatToday is really bad luck, but no matter how it is. He wanted to count his losses. Every axe of a woodcutter has a value, and the value of different axe is different. The total loss is the value and the sum of the lost axe. He thinks there are several possible solutions for every possible total loss. Note: if the water godTake away two axes: A and B, (a, b) and (B, a) as a plan. When we take three axe heads, (a, B, c), (B, C, a), (C, a, b), (C, B, and a), ((x, R, d), ((x, R, d) are regarded as a scheme.

Input

The first line is integer N, which means N has the axe. Next, n enters the N digit Ai in ascending order to indicate the value of each axe.

Output

Several rows, in ascending order, output one line x y for all possible total losses, x for loss values, y for scheme numbers.

Sample Input

4
4
5
6
7

Sample Output

4 1
5 1
6 1
7 1
9 1
10 1
11 2
12 1
13 1
15 1
16 1
17 1
18 1

\[A(x)=\sum_{i=1}^n x^{a_i}\]
\[B(x)=\sum_{i=1}^n x^{2a_i}\]
\[C(x)=\sum_{i=1}^n x^{3a_i}\]
The following are discussed first.
So the first thing to do is to choose one.\(A(x)\)。
Two selected are\(A(x)^2\)，And it needs to be subtracted.\((a_i,a_i)\)This is also the case.\(B(x)\)，Then choose two:\(A^2(x)-B(x)\)。
Choose the three one that needs to be subtracted (a_i, a_i, a_j).\((a_i,a_i,a_i)\)The situation has been reduced by two times.\(A^3(x)-3A(x)B(x)+2C(x)\)。
So the final answer is:\[\frac{A^3(x)-3A(x)B(x)+2C(x)}{6}+\frac{A^2(x)-B(x)}{2}+A(x)\]
FFTYou can do that.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
 
using namespace std;
#define LL long long
#define Pi 3.1415926535
 
inline int read(){
    int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int MAXN = 1000010;
const int INF = 2147483600;
 
int l,r[MAXN+1],lim=1;
struct cpx{
    double a,b;
    cpx (double aa=0,double bb=0){a=aa; b=bb;}
}a[MAXN+1],b[MAXN+1],c[MAXN+1];
int rev[MAXN+1];
cpx operator + (cpx a,cpx b){return cpx(a.a+b.a , a.b+b.b);}
cpx operator - (cpx a,cpx b){return cpx(a.a-b.a , a.b-b.b);}
cpx operator / (cpx a,double b){return cpx(a.a / b , a.b / b);}
cpx operator * (cpx a,double b){return cpx(a.a * b , a.b * b);}
cpx operator * (cpx a,cpx b){return cpx(a.a*b.a - a.b*b.b , a.a*b.b + a.b*b.a);}
 
inline void FFT(cpx *A,int type){
    for(int i=0;i<lim;i++) if(rev[i]>i) swap(A[rev[i]],A[i]);
    for(int mid=1;mid<lim;mid<<=1){
        cpx Wn(1.0*cos(Pi/mid) , 1.0*type*sin(Pi/mid));
        for(int R=mid<<1,j=0;j<lim;j+=R){
            cpx w(1,0);
            for(int k=0;k<mid;k++,w=w*Wn){
                cpx x = A[k+j] , y = w*A[k+j+mid];
                A[k+j]=x+y; A[k+j+mid]=x-y;
            }
        }
    } return ;
}
int N,k[MAXN+1],Mx=-INF;
 
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    N=read();
    for(int i=1;i<=N;i++) {
        k[i]=read(),a[k[i]].a+=1;
        b[2*k[i]].a+=1; c[3*k[i]].a+=1;
        Mx=max(Mx,3*k[i]);
    } 
    while(lim<=Mx*3) lim<<=1,++l;
    for(int i=0;i<lim;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    FFT(a,1); FFT(b,1); FFT(c,1);
    for(int i=0;i<lim;i++) a[i]=(a[i]*a[i]*a[i]-3.0*a[i]*b[i]+2.0*c[i])/6.0+(a[i]*a[i]-b[i])/2.0+a[i];
    FFT(a,-1);
    for(int i=1;i<lim;i++){
        LL num=(LL)((a[i].a/lim)+0.5); // cout<<a[i].a<<" "<<lim<<"true"<<endl;
        if(num!=0) printf("%d %lld\n",i,num);
    }
    return 0;
}