题解 AT5149 【[AGC036F] Square Constraints】

Sol1 · 2020-11-22 15:11:07 · 题解

upd. 感谢 Yoralen 的提醒，有一个地方连乘打成了连加，现已修正。

EI 在课上讲的神仙题，掉线了一节课之后回家补上了。

0 转化

题目的要求相当于：

在两个圆之间的圆环区域中放置 2n-1 个车，要求车都放在整点上，且互不攻击，求方案数，任意模数。

1 弱化

如果里面的圆不存在，此时方案数是多少？

为了方便，记 L_i=\lceil\sqrt{n^2-i^2}\rceil，R_i=\lfloor\sqrt{4n^2-i^2}\rfloor。

此时可以在圆内画出图中的几条线段。

显然，每一个车放在一条线段上，并且不能在同一横排。

那么就先考虑最短线段（即第 2n-1 条线段）上面的车，此时有 R_{2n-1}+1 种方案。

在决策完这个车放在哪里之后，剩下的每一条线段都会少一个可以放的位置。

对第二短的线段重复一遍这个过程，可以发现也会让剩下的每一条线段少一个可以放的位置。

因此，如果设 R 排序后的数组为 R'，那么方案数就是：

\prod_{i=0}^{2n-1}R'_i-i+1

2 容斥

既然对于没有下限的问题有了一个快速解法，那么这个解法是否有可能应用到有下限的问题中呢？

不满足要求的方案数也是前缀，这引诱我们进行容斥。（引用 EI 原话）

如果恰有 k 个元素的上界是 L_i-1，那么这个方案数对答案的贡献就是 (-1)^k\times f_k。

考虑 DP 出 f_k。

3 DP

因为现在上界是 L_i-1，所以 [0,n) 内的元素取关键字为 L_i-1，[n,2n) 内的元素取关键字为 R_i 进行排序。

现在我们得到了一个排好序的数组，就可以进行 DP 了。

设 f_{i,j} 为 DP 到前 i 个，并且有 j 个选择 L-1 作为上界的元素的总方案数。

显然有 f_{0,0}=1。

下面考虑每一个元素。

如果这个元素没有下界，即原本处于区间 [n,2n) 之间，那么它的方案数可以这么考虑：

原本有 R_i+1 个方案；
它前面的选择 L-1 的，由于排序保证了它小于 R_i，所以每一个限制掉一个方案。这类会限制掉 j 个方案；
它前面的没有下界的，同样是由于排序；这个需要在 DP 过程中统计，设其为 c_1。

所以可行的决策数为 R_i+1-j-c_1。有转移：

f_{i+1,j}\leftarrow f_{i,j}\cdot(R_i+1-j-c_1)

然后考虑有下界的情况。这类要分开讨论。

如果取上界为 L_i-1，则：

原本有 L_i 个方案；
它前面的选择 L-1 的和没有下界的，限制住 c_1+j 个方案。

可行决策有 L_i-c_1-j 个。有转移：

f_{i+1,j+1}\leftarrow f_{i,j}\cdot (L_i-c_1-j)

如果取上界为 R，则：

原本有 R_i+1 个方案；
关键性质：由于在 [0,n) 内，最小的 R 是 \sqrt 2n 大于最大的 L，所以任何有下界且选择 L-1 的元素都一定会影响这里的决策。
由于这个性质的存在，所以这一类的限制为 k。
此时的 R 大于所有满足 i\in [n,2n) 的 R_i，每一个都产生限制，限制为 n。
如果有下界的取上界为 R，那么在这个元素之前的也会影响决策。为了统计这个方案数，可以统计之前有下界的元素数量，设其为 c_2，则这里限制为 c_2-j。

故可行决策有 R_i+1-n-k-c_2+j 个。转移：

f_{i+1,j}\leftarrow f_{i,j}\cdot (R_i+1-n-k-c_2+j)

答案即为 f_{2n,k}。

DP 的复杂度为 O(n^2)，前面还要枚举一个 k，所以最终时间复杂度 O(n^3)，空间复杂度 O(n^2)，可以通过本题。

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
    register char c = getchar();
    register int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

inline int Abs(const int& x) {return (x > 0 ? x : -x);}
inline int Max(const int& x, const int& y) {return (x > y ? x : y);}
inline int Min(const int& x, const int& y) {return (x < y ? x : y);}

int n, mod, dp[505][505];
pair <int, int> p[505];

inline void Prefix() {
    for (int i = 0;i < n;i++) {
        p[i + 1].first = ceil(sqrt(n * n - i * i)) - 1;
        p[i + 1].second = floor(sqrt(4 * n * n - i * i));
        if (p[i + 1].second > 2 * n - 1) p[i + 1].second = 2 * n - 1;
    }
    for (int i = n;i < 2 * n;i++) {
        p[i + 1].first = floor(sqrt(4 * n * n - i * i));
        if (p[i + 1].first > 2 * n - 1) p[i + 1].first = 2 * n - 1;
        p[i + 1].second = 0;
    }
    sort(p + 1, p + 2 * n + 1);
}

inline int Calc(int k) {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    int limcnt = 0, cntr = 0;
    for (int i = 1;i <= 2 * n;i++) {
        if (p[i].second == 0) {
            for (int j = 0;j <= limcnt;j++) dp[i][j] = (dp[i][j] + 1ll * dp[i - 1][j] * (p[i].first - cntr - j + 1) % mod) % mod;
            cntr++;
        } else {
            for (int j = 0;j <= limcnt;j++) {
                dp[i][j] = (dp[i][j] + 1ll * dp[i - 1][j] * (p[i].second + 1 - n - k - limcnt + j) % mod) % mod;
                dp[i][j + 1] = (dp[i][j + 1] + 1ll * dp[i - 1][j] * (p[i].first - cntr - j + 1) % mod) % mod;
            }
            limcnt++;
        }
    }
    return dp[2 * n][k];
}

inline void Solve() {
    long long 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", Calc(i));
    }
    printf("%lld", ans);
}

int main() {
    n = qread(); mod = qread();
    Prefix();
    Solve();
    #ifndef ONLINE_JUDGE
    while (1);
    #endif
    return 0;
}