#多重集组合数# CF451E Devu and Flowers

Title

CF451E Devu and Flowers

Solution

注意code中出现的锅
注意求组合数时通常会忘记判断一些边界的东西

不考虑$n_i$的限制，从$S$中任选$r$个元素，方法数为$C_{k+r?1}^{k?1}$
根据容斥定理，至少有一种$a_i$选取的数量超过$n_i$限制的多重集共有
$$\left|\underset{i=1}{\overset{k}{?}}{S}_i\right|=\sum _{i=1}^k{\mathbb{C}}_{k+r?n_i?2}^{k?1}?\sum _{i=1}^k{\mathbb{C}}_{k+r?n_i?n_j?3}^{k?1}+?+(?1{)}^{k+1}{\mathbb{C}}_{k+r?{\sum }_{i=1}^k?(k+1)}^{k?1}$$
满足所有限制的合法多重集共有$$C_{k+r?1}^{k?1}?\left|\underset{i=1}{\overset{k}{?}}{S}_i\right|$$

具体实现中，可以枚举$0?2^N?1$
$x$在二进制中的有$p$为是$1$的，表示$$(?1{)}^p{\mathbb{C}}_{N+M?A{i}_1?A{i}_2???A{i}_p?(p+1)}^{N?1}$$
其中特殊的把$x=0$看作$C_{k+r?1}^{k?1}$

注意题目中n的范围比较小，m的比较大
所以考虑用$Lucas$定理
$${\mathbb{C}}_N^{M}modp={\mathbb{C}}_{Nmodp}^{Mmodp}?{\mathbb{C}}_{N/p}^{M/p}(modp)$$

因为后面一项为$1$，所以就相当于$Nmodp$一下，避免爆炸。

逆元的话，可以线性求，似乎没有必要，毕竟N那么小 。
阶乘不太好预处理，就那样吧。

Code

#include<cstdio>
#include<algorithm>
#define ll long long 
#define rep(i,x,y) for(register ll i=x;i<=y;++i)
using namespace std; 
const ll mod=1e9+7,N=25; 
ll a[N],inv[N],ans; ll ff[N]; 
ll C(ll n,ll m){
    if (n<0||m<0||n<m) return 0; // it usually will be ignoredn%=mod; // the special form of lucas theorem if (n==0||m==0) return 1; // it usually will be ugnored ll val=1; rep(i,0,m-1) val=val*(n-i)%mod; //factorial
// rep(i,1,m) val=val*inv[i]%mod; 
// return val; return val*ff[m]%mod; 
}/* ll ksm(ll x,ll y){ll val=1; for(;y;y>>=1,x=(x*x)%mod) if (y&1) val=(val*x)%mod; return val; }*/
int main(){
    ll n,m; scanf("%lld%lld",&n,&m); rep(i,1,n) scanf("%lld",&a[i]); ff[1]=inv[1]=1; rep(i,2,n) inv[i]=(mod-mod/i)*inv[mod%i]%mod,ff[i]=ff[i-1]*inv[i]%mod; //linear inv
// rep(i,1,n) inv[i]=ksm(i,mod-2); //normal invans=C(n+m-1,n-1)%mod; rep(i,1,(1<<n)-1) {
    ll t=n+m,p=0; rep(j,0,n-1) if ((i>>j)&1) p++,t-=a[j+1]; ans=(ans+((p&1)?-1:1)*C((t-(p+1)),n-1))%mod; }printf("%lld",(ans+mod)%mod); return 0; 
}