题目链接:Codeforces 451E Devu and Flowers
题目大意:有n个花坛,要选s支花,每个花坛有f[i]支花。同一个花坛的花颜色相同,不同花坛的花颜色不同,问说可以有多少种组合。
解题思路:2n的状态,枚举说那些花坛的花取超过了,剩下的用C(n−1sum+n−1)隔板法计算个数,注意奇数的位置要用减的,偶数的位置用加的,容斥原理。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
ll qPow (ll a, ll k, ll p) {
ll ans = 1;
while (k) {
if (k&1)
ans = (ans * a) % p;
a = (a * a) % p;
k /= 2;
}
return ans;
}
ll C (ll a, ll b, ll p) {
if (a < b)
return 0;
if (b > a - b)
b = a - b;
ll up = 1, down = 1;
for (ll i = 0; i < b; i++) {
up = up * (a-i) % p;
down = down * (i+1) % p;
}
return up * qPow(down, p-2, p) % p;
}
ll lucas (ll a, ll b, ll p) {
if (b == 0)
return 1;
return C(a%p, b%p, p) * lucas(a/p, b/p, p) % p;
}
const int maxn = 25;
const ll mod = 1e9+7;
int n;
ll s, f[maxn];
ll solve () {
ll ans = 0;
for (int i = 0; i < (1<<n); i++) {
ll sign = 1, sum = s;
for (int j = 0; j < n; j++) {
if (i&(1<<j)) {
sum -= (f[j]+1);
sign *= -1;
}
}
if (sum < 0)
continue;
ans += sign * lucas(sum + n - 1, n - 1, mod);
ans %= mod;
}
return (ans + mod) % mod;
}
int main () {
scanf("%d%lld", &n, &s);
for (int i = 0; i < n; i++)
scanf("%lld", &f[i]);
printf("%lld\n", solve());
return 0;
}
分享到:
相关推荐
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 185A - Plant 全测试点49个
E. Array Shrinking time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given an array a1,a2,…,an. You can perform the following operation...
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
题目大意:给出 n 个数字组成的序列,现在可以对数列进行多次操作,每次操作可以选择其中一段连续的数列,用其平均数替换原位置,换句话说,若原连续数列为 1 2 3,则可以替换为 2 2 2,问如何操作可以使得最后答案...
Some of the Codeforces problems codes
CodeForces :bar_chart: 使用Java
Codeforces round 678 D2_Codeforces_源码
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
打codeforces的神器
codeforces-js Codeforces JS
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
Codeforces Round #723 (Div. 2).md