题目
有下面这样的一个网格棋盘， 表示了对应边长度，也就是对应格子数：
当 时，对应下面这样一个棋盘：
要在这个棋盘上放 个相互不攻击的车，也就是这 个车没有两个车在同一行，也没有两个车在同一列，问有多少种方案。
数据规模与约定（洛谷）
- 存在部分数据，保证 ；
- 存在部分数据，保证 。
- 对于 的数据，保证 ，且至少有一种可行方案。
数据规模与约定（SDOI）
- 对于 的数据，保证 ；
- 对于 的数据，保证 ；
- 对于 的数据，保证 ；
- 对于 的数据，保证 ，且至少有一种可行方案。
题解
哦，是棋盘！
哦，是车！
那肯定是图论行列建模套匈牙利二分图最大匹配，走起！
当然，这道题目问的不是能放多少车，所以只能组合计数了！
- 按行列处理；
- 根据样例车与车不同；
- 共在 中选 列，在 中选 行
则对于一个 矩形内部放置 辆车的方法：
- 所以把棋盘分成 两个矩形计算；
- 考虑棋盘间的干扰，下面的矩形可选列数为 ；
- 对于不同的车辆数分配方案进行求和，注意边界条件， 最少分配和最多分配多少；
答案表达式为：
$$
\text{ans} =
\sum_{i = \max(0,k-d)}^{\min(a,b,k)}
C_{a}^{i} \cdot C_{b}^{i} \cdot A_i^i
\times
C_{a + c - i}^{k - i} \cdot C_{d}^{k - i} \cdot A_{k - i}^{k - i}
$$
- 考虑对于 SDOI 的
毒瘤数据进行计算优化；
- 注意到时间复杂度主要在于与 有关的 上；
- 注意到
mod = 1e5 + 3; 很小；
- 已知卢卡斯定理
Lucas 可以将 参数优化至 mod 大小以内；
$$
\binom{n}{k}
\bmod p
=
\binom{n \bmod p}{k \bmod p}
\cdot
\binom{n / p}{k / p}
\bmod p
$$
后续就很简单了，注意 fac 数组的 问题。
（六个 应该是会爆 long long 吧，我没试过 ）
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
| #include<bits/stdc++.h>
#define LL long long
const int mod = 1e5 + 3;
using namespace std;
LL a, b, c, d, k;
LL ans;
LL mul[mod];
inline void mulInit() {
mul[0] = 1;
for (int i = 1; i < mod; ++i)
mul[i] = (mul[i - 1] * i) % mod;
return;
}
inline LL Pow(LL base, LL expo) {
LL res = 1;
base %= mod;
while (expo) {
if (expo & 1)
res = (res * base) % mod;
base = (base * base) % mod;
expo >>= 1;
}
return res;
}
inline LL fac(LL x) {
return (x < mod ? mul[x] : 0);
}
inline LL Lucas(LL n, LL k) {
if (n >= mod || k >= mod) {
LL res = 1;
res = (res * Lucas(n % mod, k % mod)) % mod;
res = (res * Lucas(n / mod, k / mod)) % mod;
return res;
}
if (k < 0 || k > n)
return 0;
if (k == 0 || k == n || n == 0)
return 1;
LL upper = fac(n);
LL lower = (fac(k) * fac(n - k)) % mod;
return (upper * Pow(lower, mod - 2)) % mod;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> a >> b >> c >> d >> k;
mulInit();
for (int i = max(0LL, k - d); i <= min({a, b, k}); ++i) {
LL res1 = 1, res2 = 1;
res1 = (Lucas(a, i) * Lucas(b, i) * fac(i)) % mod;
res2 = (Lucas(a + c - i, k - i) * Lucas(d, k - i) * fac(k - i)) % mod;
ans = (ans + res1 * res2) % mod;
}
cout << ans;
return 0;
}
|
