#43462. 「计蒜客 2020.2 提高组」受力平衡
Summarize
题目概括咕咕中~
Solution
60pts
显然答案为 $\sum_{i=1}^{\min(n,m)}{n\choose i}{m\choose i}$
100pts
假设取 $i$ 个气球与 $i$ 个重物。考虑取 $i$ 个气球与 $m-i$ 个重物的方案数，与其是一一对应的。因此将题目转化为 在 $n+m$ 个物品中取 $m$ 个物品 的方案数，再排除一个气球都不选的方案数即为答案 ${n+m\choose m} -1$
Code
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int MAXN = 3e6 + 5;
int n, m;
ll fac[MAXN], inv[MAXN], facinv[MAXN];
ll C(int n, int m) {
return fac[n] * facinv[m] % MOD * facinv[n - m] % MOD;
}
ll solve(int n, int m) {
int k = min(n, m);
ll ret = 0;
for (int i = 1; i <= k; ++i)
ret = (ret + C(n, i) * C(m, i) % MOD) % MOD;
return ret;
}
int t;
int main() {
fac[0] = facinv[0] = 1;
inv[1] = fac[1] = facinv[1] = 1;
for (int i = 2; i <= 3e6; ++i) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
facinv[i] = facinv[i - 1] * inv[i] % MOD;
}
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
int x = n + 1, y = m + 1;
printf("%lld\n", C(x + y - 2, y - 1) - 1);
}
return 0;
}
|