526互联

AtCoder Grand Contest 036 F Square Constraints

发布时间 2023-10-03 21:43:29作者: zltzlt

洛谷传送门

AtCoder 传送门

本质是 \(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;
}