AT_arc197_e

cosf · 2025-07-07 20:15:17 · 题解

模拟赛遇到这个题，还以为是 arc 的 a 题呢，怎么是 e。

由于题目条件给定 H, W \le 3N - 1，因此不可能有三个并排，必然按照图中的方案排列。因此，我们只需要保留它们靠中心的四个点，按照图中顺序记为 (x_1, y_1), \dots, (x_4, y_4)：

这样，就相当于在一个 (H - 2N + 2) \times (W - 2N + 2) 上选 4 个点，满足一定条件。为了方便，下列用 h, w 代表这个新网格的长宽。

一个想法就是横纵分开。以横轴为例，图中可知 x_1 \lt x_4 和 x_2 \lt x_3。这样的选法一共有 \binom{w}{2}^2 种。因此，这部分答案是 \binom{w}{2}^2 \times \binom{h}{2}^2。

然而，这样会将一些错误答案统计进去。这是因为，我们保证了相邻数字的正方形不会相交，但是相对的两者没有保证。

如图（就别注意大小了，反正差不多一个意思），1, 3 可能相交（当然 2, 4 相交的方案数是一样的），而这就要求在横轴上有 x_2 \lt x_3 \le x_1 \lt x_4，这个方案数是 \binom{w + 1}{4}。纵轴也是一样的，因此这些记重的方案有 2 \times \binom{w + 1}{4} \times \binom{h + 1}{4} 种。

因此答案就是 \binom{w}{2}^2\binom{h}{2}^2 - 2\binom{w + 1}{4}\binom{h + 1}{4}。

注意特判。

#include <iostream>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;

using mint = modint998244353;

int n, h, w;

mint c2(mint n)
{
    return (n * (n - 1) / 2).pow(2);
}

mint c4(mint n)
{
    return ((n + 1) * n * (n - 1) * (n - 2) / 24);
}

void solve()
{
    cin >> n >> h >> w;
    if (h < 2 * n || w < 2 * n)
    {
        cout << 0 << '\n';
    }
    else
    {
        h -= 2 * n - 2;
        w -= 2 * n - 2;
        cout << (c2(h) * c2(w) - 2 * c4(h) * c4(w)).val() << '\n';
    }
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}