形式化题目

棋盘是一个 L 形（阶梯形）区域，由两个左对齐的矩形拼成：

• 上矩形：$b$ 行、$a$ 列；
• 下矩形：$d$ 行、$a+c$ 列，与上矩形共用最左边的 $a$ 列。

题面用 $a,b,c,d$ 标注四条边：$a$ 是上矩形的宽度，$b$ 是上矩形的高度，$c$ 是下矩形 比上矩形向右多伸出的宽度，$d$ 是下矩形的高度。$a=b=c=d=2$ 时的图形是：

1
2
3
4
5
6
7
8    +--+                       <- 上矩形：b=2 行、a=2 列
    |  |
    |  |
  +-+--+                       <- 下矩形顶边，以下区域总宽 a+c = 4
  |    |
  |    |                       <- 下矩形：d=2 行、a+c=4 列
  +----+
   a  c

在棋盘上放 $k$ 个互不攻击的车（国际象棋的 rook），要求任意两个车不在同一行、 也不在同一列。求合法摆放的方案数对 $100003$ 取模的结果。

数据范围：$0 \leqslant a,b,c,d,k \leqslant 1000$（题面写 $1 \leqslant$，但真实数据中存在 $0$， 例如 0 0 1000 1000 1000，实现必须容忍 $0$）。题目保证至少存在一种可行方案。

样例：$a=b=c=d=2,\ k=2$ 时答案为 $38$。

正解

思路

第一步：把“互不攻击”翻译成“行列都互不相同”。

$k$ 个车互不攻击，等价于它们占据的 $k$ 个格子两两不同行、两两不同列。 于是计数问题变成：选出 $k$ 个格子，使它们用到的行数 = 列数 = $k$。

第二步：先解决矩形，得到闭式 $f(R,C,t)$。

在 $R$ 行 $\times$ $C$ 列的矩形里放 $t$ 个互不攻击的车，可以分两步决策：

1. 选出被占用的 $t$ 行，方案数 $\binom{R}{t}$；
2. 把这 $t$ 行按行序依次配上互不相同的列：第 1 行有 $C$ 种选法，第 2 行剩 $C-1$ 种…… 共 $C(C-1)\cdots(C-t+1)=P(C,t)$ 种。

两步的决策互不影响，所以

第三步：按上矩形里放几个车来分类。

L 形棋盘没法直接用矩形闭式，但它由两个矩形拼成，而上下两块的行完全不相交。 于是按“上矩形里放了多少个车”分类是天然的切入点：枚举

表示上矩形（$b$ 行 $\times$ $a$ 列）中放了 $i$ 个车。

• 上矩形的贡献直接由闭式给出：$\binom{b}{i}P(a,i)$。
• 上矩形占用的 $i$ 列，全都落在上矩形的列集 $\{0,\dots,a-1\}$ 内； 而这个列集又是下矩形列集 $\{0,\dots,a+c-1\}$ 的子集。 所以上矩形放完车后，下矩形恰好有 $i$ 列不可用，可用列数变成 $a+c-i$。 注意这里扣减的量精确等于 $i$，与“上矩形具体占了哪 $i$ 列”无关。
• 上下两矩形的行集不相交，所以行方向不会再产生任何额外约束。
• 下矩形（$d$ 行）还要放完剩下的 $k-i$ 个车，贡献 $\binom{d}{k-i}P(a+c-i,k-i)$。

把两者相乘，对所有 $i$ 求和：

为什么这样分类不重不漏。 任何一个合法摆放，它在 $L$ 形上矩形中的车数必然是某个 $i\in[0,\min(a,b,k)]$，因此都会被统计到，无漏；而 $i$ 由上矩形内的车数唯一确定， 不同 $i$ 对应的摆放集合互不相交，无重。固定 $i$ 之后，上下两块各自都是“选行 $\times$ 分配列”的独立性论证，下矩形的可用列数又被精确扣减，所以项内计数也是正确的。

实现要点。 $a+c$ 上界是 $2000$，预处理 $\binom{n}{r}$ 与 $P(n,r)$ 到 $n=2000$ 即可。 $P(n,r)$ 是下降幂 $n(n-1)\cdots(n-r+1)$，用前缀积一次生成一整行，比每个格子单独循环快得多。 模数 $100003$ 虽是质数，但这里完全不需要求逆元——$\binom{n}{r}$ 用杨辉递推、 $P(n,r)$ 用前缀积累乘，都是 $O(n^2)$ 总代价。

下面这张表画出 $i$ 变化时两块矩形的方案数如何拆分，以样例 $a=b=c=d=2,\ k=2$ 为例 （表中的 $\binom{2}{2}=1$，注意别与 $P$ 混淆）：

上表的行就是 $i$ 的三种取值。可以看到 $i$ 每增加 $1$，下矩形的可用列数就少 $1$ （$4\to3\to2$），这正是“上矩形占掉的列与下矩形共享”的体现；三行乘积相加恰好等于 样例的 $38$。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 00:18
# update_at: 2026-10-01 00:20

import sys
from itertools import accumulate

MOD = 100003  # 题面模数 10^5 + 3


def build_tables(limit: int) -> tuple[list[list[int]], list[list[int]]]:
    """建两张下三角表：pascal[n][r] = C(n, r)，falling[n][r] = P(n, r)。

    C(n, r) 用杨辉递推；P(n, r) = n(n-1)…(n-r+1) 是下降幂，
    用前缀积（accumulate）一次算完整行，不必对每个 r 重新乘一遍。
    表只需要前 limit+1 行——最大的下标来自 a+c、b、d、k，不超过 a+c 量级。
    """
    pascal: list[list[int]] = [[1]]
    for n in range(1, limit + 1):
        prev = pascal[-1]
        pascal.append([1] + [(prev[r - 1] + prev[r]) % MOD for r in range(1, n)] + [1])

    # 前缀积的序列是 1, n, n-1, …, 1，开头补的 1 让 falling[n][0] = 1。
    falling: list[list[int]] = [
        list(accumulate([1, *range(n, 0, -1)], lambda x, y: x * y % MOD))
        for n in range(limit + 1)
    ]
    return pascal, falling


def solve() -> None:
    a, b, c, d, k = map(int, sys.stdin.buffer.read().split())

    # 组合/排列的顶层下标只会是 b、a+c、d、k 之一，取最大者即为表的规模。
    pascal, falling = build_tables(max(b, a + c, d, k))

    def ways(rows: int, cols: int, used: int) -> int:
        """在 rows 行 × cols 列的矩形里放 used 个互不攻击的车的方案数。

        两步独立相乘：先选出被占用的 used 行，有 C(rows, used) 种；
        再给这 used 行依次分配互不相同的列，有 P(cols, used) = cols(cols-1)… 种。
        used 超过行数或列数时为 0（此时 C 或 P 的越界项不存在）。
        """
        if used < 0 or used > rows or used > cols:
            return 0
        return pascal[rows][used] * falling[cols][used] % MOD

    # 枚举上矩形（b 行 × a 列）里放 i 个车。
    # 上矩形占用的 i 列都在它的列集内，而下矩形（d 行 × (a+c) 列）的列集
    # 完整包含这个列集，所以下矩形恰好只剩 a + c - i 列可用；行互不相交，无别的耦合。
    ans = sum(
        ways(b, a, i) * ways(d, a + c - i, k - i) % MOD
        for i in range(min(a, b, k) + 1)
    )
    print(ans % MOD)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:41
 * update_at: 2026-10-06 00:41
 */

// L 形棋盘由两个左对齐矩形拼成：上矩形 b 行 a 列，下矩形 d 行 a+c 列（共享左侧 a 列）。
// 按上矩形里放几个车 i 分类：上矩形 C(b,i)*P(a,i)，下矩形的可用列被扣成 a+c-i，
// 贡献 C(d,k-i)*P(a+c-i,k-i)，对所有 i 求和即答案。

#include <cstdio>

typedef long long ll;

const ll MOD = 100003;          // 题面模数 10^5 + 3
const ll MAXN = 2005;           // a+c 最大 2000，所有组合/排列顶层下标都不超过它

ll n_max;                       // 表实际建到的最大行数
ll C[MAXN][MAXN];               // C[n][r] = 组合数 C(n, r) mod MOD，杨辉递推生成
ll P[MAXN][MAXN];               // P[n][r] = 下降幂 n(n-1)...(n-r+1) mod MOD，前缀积累乘

// 在 R 行 * Ccol 列的矩形里放 t 个互不攻击的车的方案数：
// 先选被占用的 t 行（C(R,t)），再给这 t 行依次配互不相同的列（P(Ccol,t)），两步独立。
// t 越界（不存在的方案）返回 0。
ll ways(ll R, ll Ccol, ll t) {
    if (t < 0 || t > R || t > Ccol)
        return 0;
    return C[R][t] * P[Ccol][t] % MOD;
}

void solve() {
    ll a, b, c, d, k;
    scanf("%lld %lld %lld %lld %lld", &a, &b, &c, &d, &k);

    // 组合/排列的顶层下标只会是 b、a+c、d、k，取最大者建表
    n_max = b;
    if (a + c > n_max) n_max = a + c;
    if (d > n_max) n_max = d;
    if (k > n_max) n_max = k;

    // 杨辉递推建组合数表：C(n,0)=1，C(n,r)=C(n-1,r-1)+C(n-1,r)
    for (ll n = 0; n <= n_max; ++n) {
        C[n][0] = 1;
        for (ll r = 1; r <= n; ++r)
            C[n][r] = (C[n - 1][r - 1] + C[n - 1][r]) % MOD;
    }

    // 前缀积建下降幂表：P[n][0]=1，P[n][r]=P[n][r-1]*(n-r+1)
    for (ll n = 0; n <= n_max; ++n) {
        P[n][0] = 1;
        for (ll r = 1; r <= n; ++r)
            P[n][r] = P[n][r - 1] * (n - r + 1) % MOD;
    }

    // 枚举上矩形（b 行 a 列）里的车数 i。
    // 上矩形占用的 i 列都在它的列集 {0..a-1} 内，而这个列集是下矩形列集的子集，
    // 所以下矩形恰好剩 a+c-i 列可用；上下两块行集不相交，行方向没有别的耦合。
    ll ans = 0;
    ll i_max = a;
    if (b < i_max) i_max = b;
    if (k < i_max) i_max = k;
    for (ll i = 0; i <= i_max; ++i) {
        ll up = ways(b, a, i);              // 上矩形方案数
        ll down = ways(d, a + c - i, k - i); // 下矩形可用列只剩 a+c-i
        ans = (ans + up * down) % MOD;
    }

    printf("%lld\n", ans);
}

int main() {
    solve();
    return 0;
}

复杂度

• 时间复杂度：$O(a+c)$。表只建到 $\max(b,\,a+c,\,d,\,k)$ 行（不超过 $a+c$ 量级）， 杨辉递推与下降幂前缀积各 $O(a+c)$；枚举 $i$ 共 $\min(a,b,k)+1 \leqslant 1001$ 项， 每项 $O(1)$。与标准 C++ 正解同阶。
• 空间复杂度：$O(a+c)$ 存储两张下三角表。实测最坏一组（$a=b=c=d=1000$）耗时 $0.26$ s、峰值内存约 $173$ MB，超过本题 $128$ MB 限制，属于允许的 Python 侧 MLE 风险； 同样算法在 C++ 里用两张 int[2001][2001] 约 $32$ MB，可在限制内通过。

总结

题目把“在 L 形棋盘上放 $k$ 个互不攻击的车”化归为两个左对齐矩形的拼接。 核心结论有两条：其一，单个 $R\times C$ 矩形放 $t$ 个车的方案数是 $\binom{R}{t}P(C,t)$（选行 $\times$ 分配列）；其二，上下两块共享左侧 $a$ 列， 于是上矩形占用 $i$ 列后下矩形恰好只剩 $a+c-i$ 列可用。 按 $i$ 分类枚举求和，复杂度 $O(a+c)$，$a,b,c,d,k$ 到 $1000$ 也能瞬间出解。

图示解析

下图给出求和的整体流程：先枚举上矩形的车数 $i$，再分别用矩形闭式算出两块区域的方案数， 相乘后累加取模。重点看中间“下矩形可用列数 $a+c-i$”这一步——它是全题唯一的跨区域耦合。

flowchart TD
    Start["读入 a b c d k"] --> Pre["建表 C(n,r) 与 P(n,r)，n 到 max(b, a+c, d, k)"]
    Pre --> Loop[“枚举 i = 0 .. min(a,b,k)”]
    Loop --> Up[“上矩形 b×a：C(b,i)·P(a,i)”]
    Loop --> Down[“下矩形 d×(a+c-i)：C(d,k-i)·P(a+c-i,k-i)”]
    Up --> Mul[“两项相乘并累加取模”]
    Down --> Mul
    Mul --> More{“i 枚举完 ?”}
    More -- 否 --> Loop
    More -- 是 --> Out[“输出累加和对 100003 取模”]

矩形闭式 $f(R,C,t)=\binom{R}{t}P(C,t)$ 的来源可以在一个小矩形里看清： 选行（哪些行被占）与分配列（每行配哪一列）是两次互相独立的决策。 下面用 $R=C=2,\ t=2$ 说明这两步如何相乘：

1
2
3
4
5
6
7
8第一步：选 2 行——只有一种，两行都占     第二步：给这 2 行配 2 个不同的列
      col0 col1                              row0 可选 col0 或 col1  (2 种)
row0   [X]  [X]          C(2,2) = 1         row1 只能选剩下那列     (1 种)
row1   [X]  [X]                        P(2,2) = 2 * 1 = 2

合成：1 * 2 = 2 种，恰好是两条对角线摆法：
   X .        . X
   . X        X .

观察重点是“选行”和“分配列”之间没有先后依赖：无论先做哪一步，结果都是 $\binom{R}{t}\cdot P(C,t)$。这解释了为什么矩形闭式可以直接相乘， 而 L 形棋盘必须再按 $i$ 分类——因为上下两块在列上并不独立。