Square Constraints

xht · 2023-09-27 01:30:08 · 题解

Square Constraints

题意

• 给定 n，求满足以下条件的 0 \sim 2n-1 的排列 p_{0\dots2n-1} 的个数。
  • 对于 i \in [0,2n-1]，满足 n^2 \le i^2 + p_i^2 \le (2n)^2。

题解

本质上，这依然是一个 p_i \in [l_i,r_i] 的计数问题。

在没有下界限制的情况下，我们有个经典的做法是，将 r_i 从小到大排序，这样当考虑第 i 个数时，由于前面的 r 都 \le r_i，因此无论前面怎么填，第 i 个数的方案数都为 r_i + 1 - i（编号从 0 开始），总方案数为 \prod_{i=0}^{2n-1} r_i + 1 - i。

在有下界时，我们可以考虑容斥，设 f(k) 表示至少有 k 个数小于下界时的方案数，则答案为 \sum_{k=0}^{2n} (-1)^kf(k)。

回到本题，题意的约束条件比较奇怪，考虑将它变得直观一点就是：

• 以原点为圆心在第一象限画两个半径分别为 n,2n 的 1/4 圆，对于 i \in [0,2n-1]，(i,p_i) 必须在这两个 1/4 圆之间（含圆上）。

于是我们有 l_{n\dots2n-1} = 0，因此只有对于 i \in [0,n-1] 才有可能 p_i < l_i。

考虑枚举若干个 i 要求 p_i < l_i，则此时相当于没有下界限制的计数，用上面的方法即可。

然而显然我们不能枚举每个 i \in [0, n-1] 是否要求 p_i < l_i，有没有什么办法可以直接计算出 f(k) 呢？

注意到对 r 排序后求 \prod_{i=0}^{2n-1} r_i + 1 - i，本质上相当于对于每个 i，其贡献为，\le r_i 的数的个数（r_i+1 个），减去比 r_i 小的限制的个数（r_i 相同则钦定一个顺序）。

考虑：

• 对于 i \in[0,n-1]，以 l_i - 1 为第一关键字，r_i 为第二关键字。
• 对于 i \in [n, 2n-1]，以 r_i 为第一关键字，l_i-1 为第二关键字。

排序，设排序后的序列为 q_{1\dots2n}（注意，这里是从 1 开始编号，也只有这里从 1 开始编号）。

考虑 DP，设 f_{i,j} 表示对于 q_{1\dots i} 均满足 \le r，且其中有 j 项满足 < l 时对答案的贡献。

设 q_{1\dots i-1} 中 \in[0,n-1] 的有 t 个，考虑如何转移，观察上面那个直观的限制图：

• 若 q_i \in [0,n-1]，且只要求 p_{q_i} \le r_{q_i}，其贡献为：

  - 所有 $i \in [n,2n-1]$ 的 $r_i$（$n$ 个） - $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 的 $q$（$t$ 个） - $q_{i+1\dots 2n-1}$ 中 $\in [0,n-1]$ 且要求 $<l$ 的 $q$（$k-j$ 个） 转移：$f_{i,j}\leftarrow f_{i-1,j} \cdot (r_{q_i} + 1 - (n + t + k - j))$。

• 若 q_i \in [0,n-1]，且要求 p_{q_i} < l_{q_i}，其贡献为：

  - $q_{1\dots i-1}$ 中 $\in [n,2n-1]$ 的 $q$（$i-1-t$ 个） - $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 且要求 $<l$ 的 $q$（$j-1$ 个） 转移：$f_{i,j} \leftarrow f_{i-1,j-1} \cdot (l_{q_i} - (i-1-t+(j-1)))$。

• 若 q_{n,2n-1}，其贡献为：

  - $q_{1\dots i-1}$ 中 $\in [n,2n-1]$ 的 $q$（$i-1-t$ 个） - $q_{1\dots i-1}$ 中 $\in[0,n-1]$ 且要求 $<l$ 的 $q$（$j$ 个） 转移：$f_{i,j} \leftarrow f_{i-1,j} \cdot (r_{q_i} + 1 - (i-1-t+j))$。

时间复杂度 \mathcal O(n^3)。

代码

const int N = 507;
int n, l[N], r[N], q[N];
modint f[N][N], ans;

inline modint calc(int k) {
    f[0][0] = 1;
    for (int i = 1, t = 0; i <= n << 1; t += q[i] < n, i++)
        for (int j = 0; j <= min(min(i, k), t + (q[i] < n)); j++)
            if (q[i] < n) f[i][j] = f[i-1][j] * (r[q[i]] + 1 - (n + t + k - j)) + (j ? f[i-1][j-1] * (l[q[i]] - (i - 1 - t + (j - 1))) : 0);
            else f[i][j] = f[i-1][j] * (r[q[i]] + 1 - (i - 1 - t + j));
    return f[n<<1][k];
}

int main() {
    rd(n, P);
    for (int i = 0; i < n << 1; i++)
        l[i] = max(0, (int)ceil(sqrt(n * n - i * i))),
        r[i] = min(2 * n - 1, (int)floor(sqrt(4 * n * n - i * i))),
        q[i+1] = i;
    sort(q + 1, q + (n << 1 | 1), [&](int i, int j) {
        pi x = i < n ? mp(l[i] - 1, r[i]) : mp(r[i], l[i] - 1);
        pi y = j < n ? mp(l[j] - 1, r[j]) : mp(r[j], l[j] - 1);
        return x < y;
    });
    for (int i = 0; i <= n; i++)
        if (i & 1) ans -= calc(i);
        else ans += calc(i);
    print(ans);
    return 0;
}