Codeforces 451E 容斥原理

100 阅读 0 评论 66 点赞

我是靠谱客的博主愤怒凉面，这篇文章主要介绍Codeforces 451E 容斥原理，现在分享给大家，希望可以做个参考。

题意

传送门 Codeforces 451E

题解

多重集的组合数问题。考虑每个盒子花的数量没有限制的情况，那么组合数为
$C_{s+n-1}^{n-1}$ 可以看做在 $s + n - 1$ 个位置中插入 $n - 1$ 个隔板，每个间隔构成了 $n$ 个盒子取数的情况。需要从没有限制的取法中减去超出限制的取法的数量。设 $A_i$ 代表取法中从第 $i$ 个盒子中取出超过限制（即大于 $f_i$ ）的花的取法，那么答案为
$C_{s+n-1}^{n-1}-|bigcuplimits_{i=1}^{n}A_i |$ 根据容斥原理，求解并集的时候需要计算交集。考虑 $A_i|$ ，预取 $f_i+1$ 朵花，其余情况任取，则仍然可以使用无限制情况下多重集组合数的求法，即 $C_{s+n-1-(f_i+1)}^{n-1}$ ；同理， $|A_icap A_j|$ 取法为 $C_{s+n-1-(f_i+1+f_j+1)}^{n-1}$ 。

设从从 $n$ 个盒子中取 $k$ 个盒子的集合为 $S_k$ ，那么可以枚举集合， $|sumlimits_{k=0}^{n}S_k|=2^n$ ，集合 $S_k$ 对应项为
$(-1)^kC_{s+n-1-sumlimits_{iin S_k}(f_i+1)}^{n-1}$ 考虑到 $s$ 的值很大，而 $n$ 较小，将组合数写为
$C_{n}^{m}=frac{A_{n}^{m}}{m!}$ 此时保证组合数求解复杂度为 $O (n)$ ，使用 $L u c a s$ 定理防止 $l o n g l o n g$ 溢出。总时间复杂度为 $O(n2^n)$ 。

复制代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 25
const ll mod = 1000000007;
ll n, s, f[maxn], inv[maxn], fv[maxn];
ll C(ll n, ll m)
{
if (n < m)
return 0;
if (m == 0)
return 1;
ll res = 1;
for (ll i = n - m + 1; i <= n; ++i)
res = (res * i) % mod;
return res * fv[m] % mod;
}
ll Lucas(ll n, ll m)
{
if (n < m)
return 0;
if (m == 0)
return 1;
return C(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod;
}
int main()
{
cin >> n >> s;
for (int i = 0; i < n; ++i)
cin >> f[i];
inv[1] = fv[0] = fv[1] = 1;
for (int i = 2; i < n; ++i)
{
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
fv[i] = inv[i] * fv[i - 1] % mod;
}
ll res = 0;
for (int i = 0; i < (1 << n); ++i)
{
ll sum = 0, k = 0;
for (int j = 0; j < n; ++j)
if (i >> j & 1)
sum += f[j] + 1, ++k;
res = (res + (k & 1 ? -1 : 1) * Lucas(s + n - 1 - sum, n - 1)) % mod;
}
cout << (res + mod) % mod << endl;
return 0;
}