本质是 \(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;
}
- Constraints AtCoder Contest Square Grandconstraints atcoder contest square constraints atcoder regular contest authentic atcoder contest grand negative atcoder contest grand atcoder contest radius grand atcoder contest grand 022 atcoder contest grand 001 atcoder contest descent grand histogram atcoder contest grand atcoder contest grand 019