AtCoder

Luogu

分析

题目相当于限定只能放在两个圆中间,求放 $2n$ 个车的方案数。

事实上我们可以对每一列求出其能放置车的范围 $[L_i, R_i]$。可以发现,对于所有 $i\in[n, 2n)$,都有 $L_i = 0$。

如果所有 $L_i$ 都为 $0$,这就是一个经典问题:将 $R_i$ 从小到大排序,答案即为 $\prod_{i = 0}^{2n - 1} (R_i + 1 - i)$。

然而现在有 $n$ 个元素的 $L_i$ 不为 $0$。考虑容斥,则我们需要对每个 $k$ 求出有恰好 $k$ 个车放在了小圆 $x^2 + y^2 = n^2$ 内的方案数。

这种问题可以考虑 DP。

我们首先确定一个 DP 的顺序:对于 $[0, n)$ 中的点,设其权值为 $L_i - 1$;对于 $[n, 2n)$ 中的点,设其权值为 $R_i$;然后把所有点按照权值从小到大的顺序排序。另外可能有权值相同的情况,这时候我们规定靠右的点排在前面。这样子排序的好处下面就会看到。

现在考虑如何设状态。设 $dp_{i, j}$ 表示前 $i$ 个点、有 $j$ 个在小圆内的方案数。转移讨论一下:

  • 如果当前点在 $[n, 2n)$ 中,比它小(“$a$ 比 $b$ 小”定义为按照这种方式排序后 $a$ 排在 $b$ 的前面)的有:排在其前面的所有 $[n, 2n)$ 中的元素、排在其前面的 $[0, n)$ 中的在小圆内的元素。第一类可以直接统计出来,设为 $sr$;第二类总共有 $j$ 个。于是有转移

$$ dp_{i + 1, j} \gets_+ dp_{i, j} \times (R + 1 - (sr + j)) $$

  • 如果当前点在 $[0, n)$ 中,再进行讨论:

    • 如果当前点在小圆内,比它小的与上面的情况类似,于是有转移
      $$dp_{i + 1, j + 1} \gets_+ dp_{i, j} \times (L - (sr + j))$$
    • 如果当前点不在小圆内,比它小的有:所有小圆内的元素、所有 $[n, 2n)$ 中的元素、排在其前面的所有 $[0, n)$ 中的不在小圆内的元素。设排在其前面的 $[0, n)$ 中的元素有 $sl$ 个,则第一类有 $k$ 个、第二类有 $n$ 个、第三类有 $sl - j$ 个。于是有转移
      $$dp_{i + 1, j} \gets_+ dp_{i, j} \times (R + 1 - (k + n + sl - j))$$

$dp_{2n, k}$ 即为所求的方案数。

一次 DP 是 $\mathcal{O}(n ^ 2)$ 的,所以总时间复杂度 $\mathcal{O}(n ^ 3)$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 500 + 10;

int n, mod;
int L[N], R[N], p[N];
int dp[N][N];

int calc(int k) {
    memset(dp, 0, sizeof(dp)); dp[0][0] = 1;
    for (int i = 0, sl = 0, sr = 0; i < n << 1; ++i) {
        int x = p[i];
        if (x < n) {
            for (int j = 0; j <= sl; ++j) {
                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + 1ll * dp[i][j] * (L[x] - (sr + j))) % mod;
                dp[i + 1][j] = (dp[i + 1][j] + 1ll * dp[i][j] * (R[x] + 1 - (n + k + sl - j))) % mod;
            }
            ++sl;
        } else {
            for (int j = 0; j <= sl; ++j)
                dp[i + 1][j] = (dp[i + 1][j] + 1ll * dp[i][j] * (R[x] + 1 - (sr + j))) % mod;
            ++sr;
        }
    }
    return dp[n << 1][k];
}

int main() {
    n = read(), mod = read();
    for (int i = 0; i < n; ++i) L[i] = ceil(sqrt(n * n - i * i));
    for (int i = 0; i < n << 1; ++i) R[i] = min(2.0 * n - 1, floor(sqrt(4 * n * n - i * i)));
    for (int i = 0; i < n << 1; ++i) p[i] = i;
    sort(p, p + n + n, [](int x, int y) {
        int wx = x < n ? L[x] - 1 : R[x], wy = y < n ? L[y] - 1 : R[y];
        return wx < wy || (wx == wy && x > y);
    });
    int ans = 0;
    for (int i = 0; i <= n; ++i) {
        if (i & 1) ans = (ans - calc(i) + mod) % mod;
        else ans = (ans + calc(i)) % mod;
    }
    printf("%d\n", ans);
    return 0;
}
最后修改:2021 年 02 月 16 日 04 : 55 PM