首页 > 代码库 > Codeforces Round #258 (Div. 2)Devu and Flowers 容斥原理
Codeforces Round #258 (Div. 2)Devu and Flowers 容斥原理
题目:Codeforces Round #258 (Div. 2)Devu and Flowers
题意:n个boxes ,第i个box有fi个flowers,每个boxes中的flowers完全相同,不同boxes的flowers不同,求从n个boxes中取出s个flowers的方案数。n<=20,s<=1e14,fi<=1e12.
排列组合的题目,一解法可用容斥原理(inclusion exclusion principle) 。
有2中写法dfs和集合。下为集合写法。
#include <bits\stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
typedef long long LL;
LL invv[25];
LL inv(LL x)/// 求逆元
{
return x == 1 ? 1LL : (MOD - MOD / x) * inv (MOD % x) % MOD;
}
LL Cmn(LL n, LL m) ///求组合数
{
LL ret = 1;
for (int i = 1; i <= m; i++)
ret = (n - i + 1) % MOD * ret % MOD * invv[i] % MOD;
return ret;
}
int calc(int x)
{
int ret = 0;
while (x)
{
// x -= x & (-x);
x=x&(x-1);
ret ^= 1;
}
return ret;
}
int n;
LL s, a[25];
int main()
{
for (int i = 1; i < 25; i++) invv[i] = inv(i);
cin >> n >> s;
for (int i = 0; i < n; i++)
cin >> a[i];
int ALL = (1 << n) - 1;
LL ans = 0;
for (int i = 0; i <= ALL; i++)///遍历所有集合
{
LL nows = s;
int num = 0;///统计当前集合元素个数,以确定符号
for (int j = 0; j < n; j++)
{
if (i & (1 << j))
{
nows -= a[j] + 1;
num++;
}
}
if (nows < 0) continue;
if (num & 1)///集合含有奇数个元素,符号为-
ans -= Cmn(nows + n - 1, n - 1);
else///集合含有偶数个元素,符号为+
ans += Cmn(nows + n - 1, n - 1);
ans %= MOD;
}
cout << (ans + MOD) % MOD << endl;
return 0;
}
Codeforces Round #258 (Div. 2)Devu and Flowers 容斥原理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。