目录

题目-车的放置

在这里插入图片描述

问题分析

假设行和列都是 1000 1000 1000, 1000 ! 1000! 1000!大概是 2568 2568 2568位非常大, 不能用 d f s dfs dfs
先考虑简单情况
在这里插入图片描述
假设当前考虑的是长方形, 长方形的行是 n n n, 列是 m m m, 放置 k k k个车

  • 先从行中选择 k k k行, 方案数是 C n k C_n ^ k Cnk​
  • 因为列上也不能有两辆车, 因此对于第一个车有 m m m种选法, 第二个车 m − 1 m - 1 m−1种选法, …
  • 对于列方向上的选法是 m × ( m − 1 ) × ( m − 2 ) × . . . × ( m − k + 1 ) = m ! ( m − k ) ! m \times (m - 1) \times (m - 2) \times ... \times (m - k + 1) = \frac{m!}{(m - k)!} m×(m−1)×(m−2)×...×(m−k+1)=(m−k)!m!​, 也就是 A m k A_m ^ k Amk​
  • 因此对于规则矩形, 车的选法是 C n k ⋅ A m k C_n ^ k \cdot A_m ^ k Cnk​⋅Amk​

尝试将不规则图形划分为两个规则图形
在这里插入图片描述
枚举上面放置 i i i个车, 下面就是放置 k − i k - i k−i个车, 按照先放上半部分, 再放下半部分的顺序放置, 因为先放置上面对下面的影响是固定的
在这里插入图片描述
也就是说, 整体的方案数是
C b i ⋅ A a i ⋅ C d k − i ⋅ A a + c − i k − i C_b ^ i \cdot A_a ^ i \cdot C_d ^ {k - i} \cdot A_{a + c - i} ^ {k - i} Cbi​⋅Aai​⋅Cdk−i​⋅Aa+c−ik−i​
枚举 i i i即可

算法步骤

求组合数有四种方式, 取决于数据范围
因为求组合数和排列数都需要阶乘, 因此可以处理阶乘和阶乘的逆元计算组合数和排列数

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 2010, MOD = 100003;

int a, b, c, d, k;
LL fact[N], infact[N];

LL q_pow(LL a, LL b, LL mod) {
   
    LL ans = 1;
    a %= mod;
    while (b) {
   
        if (b & 1) ans = ans % mod * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

void init() {
   
    fact[0] = 1;
    infact[0] = q_pow(fact[0], MOD - 2, MOD);

    for (int i = 1; i < N; ++i) {
   
        fact[i] = fact[i - 1] % MOD * i % MOD;
        infact[i] = q_pow(fact[i], MOD - 2, MOD);
    }
}

LL C(int a, int b) {
   
    if (a < b) return 0;
    LL ans = fact[a] % MOD * infact[a - b] % MOD * infact[b] % MOD;
    return ans;
}

LL A(int a, int b) {
   
    if (a < b) return 0;
    LL ans = fact[a] % MOD * infact[a - b] % MOD;
    return ans;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    init();
    
    cin >> a >> b >> c >> d >> k;

    LL ans = 0;
    for (int i = 0; i <= k; ++i) {
   
        ans = (ans + C(b, i) % MOD * A(a, i) % MOD * C(d, k - i) % MOD * A(a + c - i, k - i) % MOD) % MOD;
    }

    cout << ans << '\n';
    return 0;
}