文章目录
- 题目
- 思路
- 代码
题目
DevuDevuDevu 想用花去装饰他的花园，他已经购买了nnn个箱子，第iii个箱子有fif_ifi?朵花，在同一个的箱子里的所有花是同种颜色的（所以它们没有任何其他特征）。另外，不存在两个箱子中的花是相同颜色的。 现在 DevuDevuDevu 想从这些箱子里选择sss朵花去装饰他的花园， DevuDevuDevu 想要知道，总共有多少种方式从这些箱子里取出这么多的花？因为结果有可能会很大，结果需要对 109+710^9+7109+7 取模。 DevuDevuDevu 认为至少有一个箱子中选择的花的数量不同才是两种不同的方案。
输入：
第一行：n,sn,sn,s
第二行：f1,f2,...,fnf_1,f_2,...,f_nf1?,f2?,...,fn?
数据范围：1≤n≤20,0≤s≤1014,0≤fi≤10121\le n\le20,0\le s\le10^{14},0\le f_i\le10^{12}1≤n≤20,0≤s≤1014,0≤fi?≤1012
思路
我们考虑对于第 iii 种花的生成函数：
Fi(x)=1+x+x2+...+xfi=1?xfi+11?xF_i(x)=1+x+x^2+...+x^{f_i}=\frac{1-x^{f_i+1}}{1-x}Fi?(x)=1+x+x2+...+xfi?=1?x1?xfi?+1?
那么考虑总方案数的生成函数：
G(x)=∏i=1nFi(x)=∏i=1n1?xfi+11?x=∏i=1n(1?xfi+1)(1?x)nG(x)=\prod_{i=1}^nF_i(x)=\prod_{i=1}^n\frac{1-x^{f_i+1}}{1-x}=\frac{\prod_{i=1}^n(1-x^{f_i+1})}{(1-x)^n}G(x)=i=1∏n?Fi?(x)=i=1∏n?1?x1?xfi?+1?=(1?x)n∏i=1n?(1?xfi?+1)?
然后就套路一波，因为：
H(x)=1+x+x2+...=11?xH(x)=1+x+x^2+...=\frac{1}{1-x}H(x)=1+x+x2+...=1?x1?
所以:
G(x)=(∏i=1n(1?xfi+1))?(1+x+x2+...)nG(x)=(\prod_{i=1}^n(1-x^{f_i+1}))*(1+x+x^2+...)^nG(x)=(i=1∏n?(1?xfi?+1))?(1+x+x2+...)n
那我们要求 G(x)G(x)G(x) 第 sss 项的系数 asa_sas?
我们发现右边就是不定方程的非负整数解方案数,gi=Ci+n?1ng_i=C_{i+n-1}^{n}gi?=Ci+n?1n?
左边由于 nnn 很小，所以考虑二进制枚举
我们记左边枚举所得结果为：cxpcx^pcxp那么右边应为gs?pg_{s-p}gs?p?
那么
Ans=∑Scxp?gs?pAns=\sum^Scx^p*g_{s-p}Ans=∑S?cxp?gs?p?
gig_igi?用LucasLucasLucas定理计算即可
代码
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<deque>
#include<cstdio>
#include<ctime>
#include<bitset>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
LL read(){
LL f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
#define MAXN 20
#define Mod (LL)(1e9+7)
#define INF 0x3f3f3f3f
LL f[MAXN+5];
LL Pow(LL x,LL y){
LL ret=1;while(y){
if(y&1) ret=ret*x%Mod;x=x*x%Mod;y>>=1;}return ret;
}
LL Lucas(LL n,LL m){
m=min(m,n-m);LL ret=1;while(n&&m){
LL a=1,b=1,n0=n%Mod,m0=m%Mod;for(LL i=n0;i>=n0-m0+1;i--) a=a*i%Mod;for(LL i=1;i<=m0;i++) b=b*i%Mod;ret=ret*a%Mod*Pow(b,Mod-2)%Mod;n/=Mod,m/=Mod;}return ret;
}
int main(){
int n=read();LL ans=0,s=read();for(int i=1;i<=n;i++)f[i]=read();for(int S=0;S<(1<<n);S++){
LL cnt=s,sign=1;for(int i=1;i<=n;i++)if(S&(1<<(i-1)))cnt-=f[i]+1,sign=-sign;if(cnt<0) continue;ans=(ans+sign*Lucas(n+cnt-1,n-1)%Mod)%Mod;}printf("%lld\n",(ans+Mod)%Mod);return 0;
}