Submission #16988360

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod;
void add(int &x,int y){
	x=(x+y+mod)%mod;
}
int mul(int x,int y){
	return x*y%mod;
}
int sadd(int x,int y){
	return (x+y)%mod;
}
pair<int,int> a[505];
int f[505][505];
signed main(){
	int n,l,r,cnt=0;
	cin>>n>>mod;
	l=2*n-1; r=2*n-1;
	for(int i=0;i<=2*n-1;++i){
		while(i*i + l*l >= n*n && l>=0) --l;
		while(i*i + r*r > 4*n*n && r>=0) --r;
		if(l==-1) a[++cnt]=make_pair(r+1,0);
		else a[++cnt]=make_pair(l+1,r+1);
	}
	sort(a+1,a+cnt+1);
	int ans=0;
	for(int k=0;k<=n;++k){
		memset(f,0,sizeof(f));f[0][0]=1;
		for(int i=1,F=0,g=0;i<=cnt;F+=(a[i].second!=0),g+=(a[i].second==0),++i)
			for(int j=0;j<=k;++j){
				int now=f[i-1][j];
				if(a[i].second==0) add(f[i][j],mul(now,a[i].first-g-j));
				//g表示前面参与前缀计数的,j表示容斥时参与前缀计数的
				else{
					if(j!=k) add(f[i][j+1],mul(now,a[i].first-g-j));
					add(f[i][j],mul(now,a[i].second-(F-j)-k-n));
				} 
			}
		if(k&1) add(ans,mod-f[cnt][k]);
		else add(ans,f[cnt][k]);
	}
	cout<<ans; 
	return 0;
} 

Submission Info

Judge Result