Submission #55441611

---

Source Code Expand

// LUOGU_RID: 165173523
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
#define cp complex<ld>

const int N=8.4e6+5;
const ld PI=acos(-1);
int n,m,U[N],num;
ll a[N],b[N],d[N],cnt;
cp F[N];
ld ans=0;

void FFT(cp *p,int len,int op){
  for(int i=0;i<len;i++) if(i<U[i]) swap(p[i],p[U[i]]);
  cp nw=cp(1,0),u,tmp;
  for(int k=2,lst=1;k<=len;lst=k,k<<=1){
	u=cp(cos(2*PI/k),op*sin(2*PI/k));
	for(int i=0;i<len;i+=k){
	  nw=cp(1,0);
	  for(int l=i;l<i+lst;l++,nw=nw*u)
	    tmp=nw*p[l+lst],p[l+lst]=p[l]-tmp,p[l]+=tmp;
	}
  }
}

void Mul(ll *a,ll *b,int n,int m){
  int P=1;
  for(P=1;P<n+m;P<<=1);
  for(int i=n;i<P;i++) a[i]=0;
  for(int i=m;i<P;i++) b[i]=0;
  for(int i=0;i<P;i++) U[i]=(U[i>>1]>>1)|((i&1)?P>>1:0),F[i]={(ld)a[i],(ld)b[i]};
  FFT(F,P,1);
  for(int i=0;i<P;i++) F[i]=F[i]*F[i];
  FFT(F,P,-1);

  for(int i=0;i<P;i++) a[i]=(ll)(F[i].imag()/P/2+0.4999);
}

int id(int x,int y){return x*2*n+y;}

int main(){
  /*2024.7.11 H_W_Y AT_icpc2013spring_f Point Distance FFT*/
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n;m=2*n*n;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
	  cin>>a[id(i,j)],cnt+=a[id(i,j)];
  for(int i=0;i<=m;i++) b[m-i]=a[i];

  Mul(a,b,m+1,m+1);

  for(int i=0;i<=m;i++){
	int x=(m-i)/(2*n),y=(m-i)%(2*n);
	if(y>n) y=2*n-y,++x;
	// cerr<<x<<" "<<y<<endl;
	d[x*x+y*y]+=a[i];
  }
  d[0]-=cnt,d[0]/=2;
  cnt=0;
  for(int i=0;i<=m;i++) cnt+=d[i];
  for(int i=0;i<=m;i++) ans+=(ld)sqrt((ld)i)*d[i]/cnt;
  //ans/=(ld)cnt;

  cout<<fixed<<setprecision(10)<<ans<<'\n';
  num=0;
  for(int i=0;i<=m;i++){
	if(d[i]) cout<<i<<' '<<d[i]<<'\n',++num;
	if(num==10000) break;
  }
  return 0;
}

Submission Info

Judge Result