AGC 036 F

可以发现每一个\(p_i\)需要满足属于一个区间。

可以发现一个重要的性质，对于\(i\geq n\),\(l_i=0\)。且\(l_{n-1}>\max(r_i)\)。同时如果将\([l_i,r_i]\)排序，满足\(l_i,r_i\)都升序。

容斥\(<n^2\)的个数，其他满足\(\leq (2N)^2\)。

复杂度\(O(N^3)\)。

/**
 *    author:  gary
 *    created: 01.01.2022 21:15:43
**/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define rep(a,b) for(int a=0;a<b;++a)
#define LL long long
#define PB push_back
#define POB pop_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
const int MAXN=505;
int n,MOD;
int l[MAXN],r[MAXN];
mp a[MAXN+MAXN];
int dp[MAXN][MAXN];
int prefix[MAXN+MAXN];
int solve(int k){
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    rb(i,0,2*n-1){
        rb(j,0,i){
            if(dp[i][j]){
                int pre=(i==0? 0:prefix[i-1])+j;
                if(a[i].SEC==-1){
                    // cout<<a[i].FIR<<"_"<<pre<<endl;
                    if(a[i].FIR>pre)
                        (dp[i+1][j]+=1ll*dp[i][j]*(a[i].FIR-pre)%MOD)%=MOD;
                }
                else{
                    {
                        if(j<k){
                            if(a[i].FIR>pre)
                            (dp[i+1][j+1]+=1ll*dp[i][j]*(a[i].FIR-pre)%MOD)%=MOD;
                        }
                        //choose 
                    }
                    {
                        pre=i-(i==0? 0:prefix[i-1]);
                        // cout<<pre<<" "<<prefix[i-1]<<endl;
                        pre=n+k+pre-j;
                        // cout<<a[i].FIR<<" "<<r[a[i].SEC]<<" "<<pre<<endl;
                        if(r[a[i].SEC]>pre)
                        (dp[i+1][j]+=1ll*dp[i][j]*(r[a[i].SEC]-pre)%MOD)%=MOD;
                        //don't choose
                    }
                }
            }
        }
    }
    return dp[2*n][k];
}
bool cmp(mp A,mp B){
    if(A.FIR!=B.FIR) return A.FIR<B.FIR;
    if(A.SEC==-1||B.SEC==-1) return A.SEC<B.SEC;
    return r[A.SEC]<r[B.SEC];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>MOD;
    rb(i,0,2*n-1){
        r[i]=0;
        while(i*i+(r[i]*r[i])<=4*n*n) r[i]++;
        l[i]=0;
        while(i*i+(l[i]*l[i])<n*n) l[i]++;
        check_min(r[i],n*2);
        check_min(l[i],n*2);
    }
    int cnt=0;
    rep(i,n) a[cnt++]=II(l[i],i);
    rb(i,n,2*n-1) a[cnt++]=II(r[i],-1);
    sort(a,a+cnt,cmp);
    rep(i,2*n){
        prefix[i]=(a[i].SEC==-1);
        if(i){
            prefix[i]+=prefix[i-1];
        }
    }
    // int tmp=1;
    // int z=0;
    // rl(i,2*n-1,0){
    //     tmp=1ll*tmp*(r[i]-z)%MOD;
    //     z++;
    // }
    // rep(i,2*n){
    //     cout<<l[i]<<" "<<r[i]<<endl;
    // }
    // cout<<"--\n";
    // cout<<tmp<<endl;
    int answer=0;
    rb(k,0,n){
        if(k&1) (answer+=MOD-solve(k));
        else answer+=solve(k);
        answer%=MOD;
        // return 0;
        // cout<<k<<" "<<solve(k)<<endl;
    }
    cout<<answer<<endl;
    return 0;
}