文件详细信息

下载本文件

本文件的大小为 2624 字节。

//详细内容请见 https://a-learner.com/file/oi/XMOJ_3739_my_code.cpp。
#include<cstdio>
#include<cstdlib>
#include<cstring>
void read(int&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
inline int max(const int a,const int b){
	return a>b?a:b;
}
typedef long long ll;
const int maxn=200000,size=1<<17;
const ll P=998244353;
template<typename T>
inline void swap(T&a,T&b){
	T temp=a;
	a=b;
	b=temp;
}
inline void qmod(ll&x){
	x=x+((x>>63)&P);
}
ll qpow(ll a,int x=P-2){
	ll answer=1;
	while(x){
		if(x&1)answer=answer*a%P;
		a=a*a%P;
		x>>=1;
	}
	return answer;
}
const ll G=3,invG=qpow(G);
int n,a[maxn+1];
struct Poly{
	ll a[size];
	int n;
	Poly(){
		memset(a,0,sizeof(a));
		n=0;
	}
}A,B,C,ans;
int tr[size<<1];
void NTT(ll*f,int n,int type){
	for(int i=0;i<n;i++)
		if(i<tr[i])
			swap(f[i],f[tr[i]]);
	for(int p=2;p<=n;p<<=1){
		const int len=p>>1;
		const ll tG=qpow(type==1?G:invG,(P-1)/p);
		for(int k=0;k<n;k+=p){
			ll buf=1;
			for(int l=k;l<k+len;l++){
				const ll tmp=f[l+len]*buf%P;
				qmod(f[l+len]=f[l]-tmp);
				qmod(f[l]=f[l]+tmp-P);
				buf=buf*tG%P;
			}
		}
	}
	if(type==-1){
		const ll invn=qpow(n,P-2);
		for(int i=0;i<n;i++)f[i]=f[i]*invn%P;
	}
}
Poly operator*(const Poly u,const Poly v){
	Poly ans;
	ans.n=u.n+v.n;
	static ll a[size],b[size];
	int len=1;
	while(len<=ans.n)len<<=1;
	memcpy(a,u.a,sizeof(ll)*(u.n+1));
	memset(a+u.n+1,0,sizeof(ll)*(len-u.n-1));
	memcpy(b,v.a,sizeof(ll)*(v.n+1));
	memset(b+v.n+1,0,sizeof(ll)*(len-v.n-1));
	for(int i=0;i<len;i++)tr[i]=(tr[i>>1]>>1)|((i&1)?(len>>1):0);
	NTT(a,len,1),NTT(b,len,1);
	for(int i=0;i<len;i++)a[i]=a[i]*b[i]%P;
	NTT(a,len,-1);
	memcpy(ans.a,a,sizeof(ll)*len);
	return ans;
}
Poly operator*(const int u,const Poly v){
	Poly ans;
	ans.n=v.n;
	for(int i=0;i<=v.n;i++)ans.a[i]=u*v.a[i]%P;
	return ans;
}
Poly operator+(const Poly u,const Poly v){
	Poly ans;
	ans.n=max(u.n,v.n);
	for(int i=0;i<=ans.n;i++)qmod(ans.a[i]=u.a[i]+v.a[i]-P);
	return ans;
}
Poly operator-(const Poly u,const Poly v){
	Poly ans;
	ans.n=max(u.n,v.n);
	for(int i=0;i<=ans.n;i++)qmod(ans.a[i]=u.a[i]-v.a[i]);
	return ans;
}
Poly operator/(const Poly u,const int v){
	Poly ans;
	ll invv=qpow(v,P-2);
	ans.n=u.n;
	for(int i=0;i<=u.n;i++)ans.a[i]=u.a[i]*invv%P;
	return ans;
}
int main(){
	read(n);
	int val=0;
	for(int i=1;i<=n;i++){
		read(a[i]);
		A.a[a[i]]++;
		B.a[a[i]*2]++;
		C.a[a[i]*3]++;
		val=max(val,a[i]);
	}
	A.n=val,B.n=val*2,C.n=val*3;
	ans=(A*A*A-3*A*B+2*C)/6+(A*A-B)/2+A;
	for(int i=1;i<=ans.n;i++)
		if(ans.a[i])
			printf("%d %lld\n",i,ans.a[i]);
	return 0;
}