本质是 \(p_i \in [l_i, r_i]\) 的计数问题。
当 \(1 \le i \le n\) 时，\(l_i\) 才可能不等于 \(1\)。考虑容斥，设钦定 \(m\) 个不满足条件（上界为 \(l_i - 1\)），其余任意（上界为 \(r_i\)）。
然后按照上界排序后 dp，设 \(f_{i, j}\) 为考虑前 \(i\) 个元素，已经有 \(j\) 个不满足条件。设前 \(i\) 个元素中，\(id_i \in [n + 1, 2n]\) 的个数为 \(c_1\)，\(id_i \in [1, n]\) 的个数为 \(c_2\)。
当 \(id_i \in [1, n]\) 时，讨论 \(p_i\) 上界是否为 \(l_i - 1\)。
如果是，那么 \(f_{i, j} \gets f_{i - 1, j - 1} \times (r_i - (j - 1) - c_1)\)，因为有 \(c_1\) 个 \(id_i \in [n + 1, 2n]\) 的元素和 \(j - 1\) 个 \(id_i \in [1, n]\) 的元素在它之前。
如果不是，那么钦定它比 \(id_i \in [n + 1, 2n]\) 的所有元素和 \(id_i \in [1, n]\) 且上界为 \(r\) 且 \(r < r_i\) 或上界为 \(l - 1\) 的元素晚放（因为 \(r_i\) 一定大于 \(id_j \in [1, n]\) 的最大的 \(l_j\)）。那么有 \(f_{i, j} \gets f_{i - 1, j} \times (l_i - 1 - n - m - (c_2 - j))\)。
当 \(id_i \in [n + 1, 2n]\) 时，前面有 \(j\) 个数选择了 \(l\) 且都比 \(r_i\) 小，还有 \(c_1\) 个 \(id_i \in [n + 1, 2n]\) 的元素，那么 \(f_{i, j} \gets f_{i - 1, j} \times (r_i - j - c_1)\)。
最后这部分答案为 \(f_{2n, m}\)。
再乘一个容斥系数就是答案。
枚举 \(m\) 再做 \(O(n^2)\) 的 dp，时间复杂度 \(O(n^3)\)。
code
// Problem: F - Square Constraints
// Contest: AtCoder - AtCoder Grand Contest 036
// URL: https://atcoder.jp/contests/agc036/tasks/agc036_f
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 510;
ll n, mod, f[maxn][maxn];
struct node {
ll l, r, op;
} a[maxn];
inline void upd(ll &x, ll y) {
((x += y) >= mod) && (x -= mod);
}
inline ll calc(ll m) {
mems(f, 0);
f[0][0] = 1;
ll c1 = 0, c2 = 0;
for (int i = 1; i <= n * 2; ++i) {
if (a[i].op) {
for (int j = 0; j <= m; ++j) {
f[i][j] = f[i - 1][j] * max(a[i].r - j - c1, 0LL) % mod;
}
++c1;
} else {
for (int j = 0; j <= m; ++j) {
f[i][j] = f[i - 1][j] * max(a[i].l - n - m - (c2 - j), 0LL) % mod;
if (j) {
upd(f[i][j], f[i - 1][j - 1] * max(a[i].r - (j - 1) - c1, 0LL) % mod);
}
}
++c2;
}
}
return f[n * 2][m];
}
void solve() {
scanf("%lld%lld", &n, &mod);
for (int i = 1; i <= n * 2; ++i) {
a[i].op = (i > n);
for (int j = 1; j <= n * 2; ++j) {
if ((i - 1) * (i - 1) + (j - 1) * (j - 1) >= n * n) {
a[i].l = j;
break;
}
}
a[i].r = n * 2;
for (int j = 1; j <= n * 2; ++j) {
if ((i - 1) * (i - 1) + (j - 1) * (j - 1) > n * n * 4) {
a[i].r = j - 1;
break;
}
}
if (i <= n) {
swap(a[i].l, a[i].r);
--a[i].r;
}
}
sort(a + 1, a + n * 2 + 1, [&](const node &a, const node &b) {
return a.r < b.r || (a.r == b.r && a.l < b.l);
});
ll ans = 0;
for (int i = 0; i <= n; ++i) {
ans = (ans + ((i & 1) ? mod - 1 : 1) * calc(i) % mod) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}