Devu and Flowers

NC230894. Devu and Flowers

描述

Devu 想用花去装饰他的花园，他已经购买了 $n$ 个箱子，第 $i$ 个箱子有 $f_i$ 朵花，在同一个的箱子里的所有花是同种颜色的（所以它们没有任何其他特征）。另外，不存在两个箱子中的花是相同颜色的。

现在 Devu 想从这些箱子里选择 $s$ 朵花去装饰他的花园，Devu 想要知道，总共有多少种方式从这些箱子里取出这么多的花？因为结果有可能会很大，结果需要对 $10^9+7$ 取模。 Devu 认为至少有一个箱子中选择的花的数量不同才是两种不同的方案。

输入描述

第一行包含两个用空格分开的整数和，。
第二行包含个用空格分开的整数。

输出描述

输出一个整数表示答案。

示例1

输入:

2 3
1 3

输出:

说明:

样例1：选3朵花两种方案：1,2 和 0,3

示例2

输入:

2 4
2 2

输出:

说明:

样例2：选4朵花只有一种方案：2,2

示例3

输入:

3 5
1 3 2

输出:

说明:

样例3：选5朵花三种方案：1,2,2 和 0,3,2 和 1,3,1

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 119ms, 内存消耗: 476K, 提交时间: 2023-03-10 14:25:55

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll n,s,jc=1,m[25],ans;
ll qpow(ll a,ll b,ll mod){
	ll ans=1;
	a%=mod;
	while(b){
		if(b&1)	ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans%mod;
}
ll C(ll i){
	ll ans=1;
	for(ll j=s-i+1;j<=s-i+n-1;j++)	ans=j%mod*ans%mod;
	return ans*jc%mod;
}
void dfs(int pos,ll xishu,ll zhishu){
	if(pos==n){
		if(zhishu<=s)
			ans=((ans+xishu*C(zhishu)%mod)%mod+mod)%mod;
		return ;
	}
	dfs(pos+1,xishu,zhishu);
	dfs(pos+1,-xishu,zhishu+m[pos+1]+1);
}
int main(){
	scanf("%lld%lld",&n,&s);
	for(int i=2;i<n;i++)	jc*=i;
	jc=qpow(jc,mod-2,mod);
	for(int i=1;i<=n;i++)	scanf("%lld",&m[i]);
	dfs(0,1,0);
	printf("%lld\n",ans);
	return 0;
}