研究母函数&容斥
刚开始没发现是不重复感觉大概很麻烦...
//By Richard
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X)
#define debugout(X)
#endif
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
/////////////////////read3.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {ch=getchar();if (ch=='-') flag=true;}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
/////////////////variables&functions////////////////////
const int maxn=1048576;
const double pi=3.1415926535897932384626433832795028841971693993751058209749446,eps=0.1;
int n,m,r[maxn],l,ans[maxn],N,x,inp[maxn];
struct cp
{
double x,y;
cp(double a=0,double b=0):x(a),y(b){}
cp operator+(cp b){return cp(x+b.x,y+b.y);}
cp operator-(cp b){return cp(x-b.x,y-b.y);}
cp operator*(cp b){return cp(x*b.x-y*b.y,x*b.y+y*b.x);}
cp operator/(int b){return cp(x/b,x/b);}
}A[maxn],B[maxn],C[maxn];
inline void swap(cp &a,cp &b){cp t=a;a=b;b=t;}
void FFT(cp *a,int n,int op)
{
rep(i,0,n-1) if (i<r[i]) swap(a[i],a[r[i]]);
for (int i=1;i<n;i<<=1)
{
cp wn(cos(pi/i),sin(pi/i)*op);
for (int j=0;j<n;j+=i<<1)
{
cp w(1,0);
for (int k=0;k<i;k++,w=w*wn)
{
cp x=a[j+k],y=a[i+j+k]*w;
a[j+k]=x+y;
a[i+j+k]=x-y;
}
}
}
if (op==-1) rep(i,0,n-1) a[i]=a[i]/n;
}
void init()
{
m+=n-2;
for (n=1,l=0;n<=m;n<<=1,l++);
rep(i,0,n-1) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
}
void mult(cp *a,cp *b)
{
FFT(a,n,1);FFT(b,n,1);
rep(i,0,n-1) a[i]=a[i]*b[i];
FFT(a,n,-1);
// debugdo(rep(i,0,m) printf("%d ",int(a[i].x+0.2)));
}
int main()
{
// read(n,m);
// rep(i,0,n-1) read(A[i].x);
// rep(i,0,m-1) read(B[i].x);
// init();mult(A,B,true);
read(N);
int maxx=0;
rep(i,0,N-1)
{
read(x);
maxx=max(x,maxx);
ans[x]++;A[x].x++;
B[x].x++;inp[x]++;
}
n=maxx+1;m=maxx+1;
init();mult(A,B);
rep(i,0,m) ans[i]+=(int)((A[i].x-((i&1)?0:inp[i/2]))/2+eps);
n=m+1;m=maxx+1;
cls(B);rep(i,0,m-1) B[i].x=inp[i];
rep(i,0,n) A[i].y=0;
init();mult(A,B);
int mm=m;
for (int i=0;i<=maxx;i++) C[i<<1].x=inp[i];
n=maxx*2+1;m=maxx+1;
cls(B);rep(i,0,m-1) B[i].x=inp[i];
init();mult(C,B);
mm=max(mm,m);
rep(i,0,mm) ans[i]+=(int)((A[i].x-3*C[i].x+2*((i%3)?0:inp[i/3]))/6+eps);
rep(i,0,mm) if (ans[i]) printf("%d %d\n",i,ans[i]);
return 0;
}