题解：AT_agc036_f [AGC036F] Square Constraints

· · 题解

题目中给的东西其实就是要求排列对应的坐标点落在大圆和小圆之间求排列的数量。记 f_i 表示满足 x^2+i^2<n^2 的 x\in[0,2n)\cap\mathbb N 的数量，g_i 表示满足 x^2+i^2\le 4n^2 的 x\in[0,2n)\cap\mathbb N 的数量。则排列 p_i 的限制条件就可以看作是 \forall i,f_i\le p_i<g_i。

考虑对内圆 p_i\ge f_i 的限制做容斥，钦定排列前 n 个位置中，有 k 个位置是不满足 p_i\ge f_i，则记这样的排列的数量为 F_k 则直接容斥可得答案为 \sum\limits_{k=0}^n(-1)^kF_k。

考虑算 F_k 的值。先给一个暴力的做法，设 h_i 表示 i 位置的上限，则 h_i 要么为 f_i 要么为 g_i。考虑已知 h_i 时合法的排列 p 数量怎么算。有一个结论是，如果把 h 数组内所有值从小到大排序，则满足限制的排列数为 \prod\limits_{i=0}^{2n-1}(h_i-i)。证明考虑按照上界从小王大分配数字时，处理第 j 个位置可以使用 0\sim h_j-1 这 h_j 个数字，前面也已经使用了 j 个数字，而这 j 个数字一定在上界范围内，因此共有 h_j-j 种剩余的可用选择。因此直接枚举 h_i 的值，其中恰好有 k 个上界选的是 f_i 然后对排列数求和就得到了一个暴力的做法。

考虑进一步优化时间复杂度。容易想到 dp，套路的把所有的 f_i 和所有满足 g_i\in[n,2n) 的 g_i 按照值从小到大放到一起，然后按值从小到大做扫描线，设 dp_j 表示当前已经选择了 j 个 f_i 时的贡献，则如果当前的是一个 g_i 而在这之前已经出现了 c 个必须选择的 g_j（这里说 g_j 必须选择是指 j\ge n 的 j 此时 f_j 的限制不存在）那么当前 g_i 前面留下的数共有 c+j 个，因此 g_i 在最终排序的下标就是 c+j，其贡献就是 g_i-c-j，因此转移就是 dp_j\leftarrow dp_j(g_i-c-j)。

然后考虑如果当前遇到了一个 f_i，则需要进一步分类讨论：

如果选 f_i 则她前面已经有 y+j 个被选中的数，所以其的贡献就是 f_i-y-j，因此转移就形如 dp'_{j+1}\leftarrow dp'_{j+1}+dp_j(f_i-y-j)。

如果不选 f_i 则之后就必须选对应的 g_i，考虑贡献提前处理，对应 g_i 的位置已经是确定的了，因此固定最终选 k 个 f 加上 n 个必须选的 g，这些大 g_i 前面一定有 n+k 个数，而当前之前已经经过了 x 个 f，其中只有 j 个 f 被选，所以共有 x-j 个 f 被放弃了，她们对应的 g 都会排在当前这个 g_i 的前面，因此当前这个 g_i 的最终下标就是 n+k+x-j，其贡献就是 g_i-n-k-x+j，转移就形如 dp'_{j+1}\leftarrow dp'_{j+1}+dp_j(g_i-n-k-x+j)。最后更新 dp\leftarrow dp' 即可。

扫描完之后 dp_k 就是恰好选 k 个 f_i 的总共先，也就是 F_k。代入上面的容斥式子直接算答案即可，总时间复杂度为 O(n^3)。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int F[N], nF[N];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, mod; cin >> n >> mod;
    vector<pair<int, int>> a;
    for (int i = 0; i < n; ++i) {
        int l = 0, r = 2 * n - 1;
        while ((l + 1) * (l + 1) + i * i < n * n) ++l;
        while (r * r + i * i > 4 * n * n) --r;
        a.emplace_back(l, r);
    }
    for (int i = n; i < 2 * n; ++i) {
        int r = 2 * n - 1;
        while (r * r + i * i > 4 * n * n) --r;
        a.emplace_back(r, 0);
    }
    sort(a.begin(), a.end());
    function<int(int)> calc = [&](int k) {
        fill(F, F + n + 1, 0), F[0] = 1;
        int c1 = 0, c2 = 0;
        for (auto &[l, r] : a) {
            fill(nF, nF + n + 1, 0);
            if (!r) {
                for (int j = 0; j <= c2; ++j) nF[j] = F[j] * (l - c1 - j + 1) % mod;
                ++c1;
            } else {
                for (int j = 0; j <= c2; ++j) nF[j + 1] = (nF[j + 1] + F[j] * (l - c1 - j + 1) % mod) % mod, nF[j] = (nF[j] + F[j] * (r - (n + c2 - j + k) + 1) % mod) % mod;
                ++c2;
            } copy(nF, nF + n + 1, F);
        } return F[k];
    };
    int res = 0;
    for (int k = 0; k <= n; ++k)
        if (k & 1) res = (res - calc(k) + mod) % mod;
        else res = (res + calc(k)) % mod;
    cout << res << '\n';
}

} // namespace lowspeed_song

:::