#数论，组合，容斥原理，lucas定理，乘法逆元#洛谷 CF451E Devu and Flowers

本文主要是介绍#数论，组合，容斥原理，lucas定理，乘法逆元#洛谷 CF451E Devu and Flowers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

$n$ 种颜色，每种颜色有 $a_i$ 枝花，现挑出 $m$ 朵，使没有颜色完全相同的方案

分析

可以发现，这道题是求多重集的组合数，根据容斥原理也就是
$C_{k+r-1}^{k-1}-\sum_{i=1}^kC_{k+r-n_i-2}^{k-1}+\sum_{1\leq i<j\leq k}C^{k-1}_{k+r-n_i-n_j-3}-\cdots+(-1)^kC_{k+r-\sum_{i=1}^kn_i-(k+1)}$
关于优化的方面，因为选择的数量特别大，所以说需要用二进制优化，还是比较简单去想的，对于判断越界可以用lucas定理@my blog古代猪文，关于组合数的求法可以用乘法逆元

代码

#include <cstdio>
#define rr register
#define mod 1000000007
long long m,a[20],ans; int n,inv[20];
inline int ksm(int x,int y){//快速幂int ans=1;while (y){if (y&1) ans=(long long)ans*x%mod;x=(long long)x*x%mod; y>>=1;}return ans;
}
inline int c(long long n,int m){if (n<0||m<0||n<m) return 0;//不可能存在答案if (!n||!m) return 1;//特判int ans=1;for (rr int i=0;i<m;++i)ans=(long long)ans*(n-i)%mod*inv[i]%mod;//求组合数return ans;
}
int main(){scanf("%d%lld",&n,&m);for (rr int i=0;i<n;++i) scanf("%lld",&a[i]),inv[i]=ksm(i+1,mod-2);//乘法逆元for (rr int x=0;x<1<<n;++x){if (!x) ans=(ans+c((n+m-1)%mod,n-1))%mod;//不考虑重复的状况else{long long t=n+m; int p=0;for (rr int i=0;i<n;++i)if (x>>i&1) p++,t-=a[i];//记录1的个数t-=p+1;if (p&1) ans=(ans-c(t%mod,n-1))%mod;//求答案else ans=(ans+c(t%mod,n-1))%mod;//可能要加回去（容斥定理）}}printf("%lld",(ans+mod)%mod);//算下来可能会出现负数return 0;
}