车的放置(Placing Rooks) 题解

思路分析

将 L 形棋盘按水平线切分为上方的 $a \times b$ 矩形（宽 $a$ 列、高 $b$ 行）和下方的 $(a + c) \times d$ 矩形（宽 $a + c$ 列、高 $d$ 行）。枚举上方矩形放置 $i$ 个车（$0 \le i \le k$）：

1. 在上方选 $i$ 行 $i$ 列并排列配对，方案数为 $\mathrm{C}_b^i \cdot \mathrm{C}_a^i \cdot i!$；
2. 下方需放 $k - i$ 个车，此时上方用掉的 $i$ 列不能再放，故下方剩余可用列数为 $a + c - i$，方案数为 $\mathrm{C}_d^{k-i} \cdot \mathrm{C}_{a+c-i}^{k-i} \cdot (k - i)!$。 对所有合法的 $i$ 求和并对质数 $100003$ 取模即可。预处理阶乘与组合数后时间复杂度 $O(N^2)$ 或 $O(N)$。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

const int MOD = 100003;
const int MX = 2005;
int C[MX][MX];
int fact[MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b, c, d, k;
    if (!(cin >> a >> b >> c >> d >> k)) return 0;

    for (int n = 0; n < MX; ++n)
    {
        C[n][0] = 1;
        for (int r = 1; r <= n; ++r)
            C[n][r] = (C[n - 1][r - 1] + C[n - 1][r]) % MOD;
    }
    fact[0] = 1;
    for (int i = 1; i < MX; ++i) fact[i] = (1LL * fact[i - 1] * i) % MOD;

    long long ans = 0;
    for (int i = 0; i <= k; ++i)
    {
        if (i > a || i > b) continue;
        int rem = k - i;
        if (rem > d || rem > a + c - i) continue;
        long long topWays = 1LL * C[b][i] * C[a][i] % MOD * fact[i] % MOD;
        long long botWays = 1LL * C[d][rem] * C[a + c - i][rem] % MOD * fact[rem] % MOD;
        ans = (ans + topWays * botWays) % MOD;
    }
    cout << ans << "\n";
    return 0;
}