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}-|\bigcup _{i=1}^n{A}_i|$$ 根据容斥原理，求解并集的时候需要计算交集。考虑 $|A_i|$，预取 $f_i+1$ 朵花，其余情况任取，则仍然可以使用无限制情况下多重集组合数的求法，即 $C_{s+n-1-(f_i+1)}^{n-1}$；同理，$|A_i\cap A_j|$ 取法为 $C_{s+n-1-(f_i+1+f_j+1)}^{n-1}$。

设从从 $n$ 个盒子中取 $k$ 个盒子的集合为 $S_k$，那么可以枚举集合，$|\sum _{k=0}^n{S}_k|=2^n$，集合 $S_k$ 对应项为
$$(-1{)}^k{C}_{s+n-1-\sum _{i\in S_k}(f_i+1)}^{n-1}$$ 考虑到 $s$ 的值很大，而 $n$ 较小，将组合数写为
$$C_n^m=\frac{A_n^m}{m!}$$ 此时保证组合数求解复杂度为 $O(n)$，使用 $Lucas$ 定理防止 $longlong$ 溢出。总时间复杂度为 $O(n{2}^n)$。

#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;
}

最后

以上就是愤怒凉面为你收集整理的Codeforces 451E 容斥原理的全部内容，希望文章能够帮你解决Codeforces 451E 容斥原理所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。