影响网站用户体验,装修做劳务去哪个网站找工地,wordpress 交友模板,百度做网站和推广效果怎么样4710 [Jsoi2011]分特产 题意 给定\(n\)个集合#xff0c;每个集合有相同的\(a_i\)个元素#xff0c;不同的集合的元素不同。将所有的元素分给\(m\)个不同位置#xff0c;要求每个位置至少有一个元素#xff0c;求分配方案数。 先考虑两个简单的问题 给定\(m\)个相同元素和\…4710 [Jsoi2011]分特产 题意 给定\(n\)个集合每个集合有相同的\(a_i\)个元素不同的集合的元素不同。将所有的元素分给\(m\)个不同位置要求每个位置至少有一个元素求分配方案数。 先考虑两个简单的问题 给定\(m\)个相同元素和\(n\)个不同位置每个位置至少分一个的方案数 使用插板法等价于在\(m-1\)个空挡里插\(n-1\)个元素方案数为 \[\binom{m-1}{n-1}\] 但是这样考虑这个题目是做不了的。 给定\(m\)个相同元素和\(n\)个不同位置每个位置可以不分的方案数 事实上还是插板但可以一个位置插两个板子。 把\(m\)个元素看做\(1\)把\(n-1\)个插开点看做\(0\)等价于从\(mn-1\)个元素拿\(n-1\)个方案数为 \[\binom{mn-1}{n-1}\] 从问题\(2\)出发我们就可以容斥了 把一种方案有几个位置没选作为方案的性质我们可以计算出一个至少有几个人没选的方案集合的数量。 因为位置的计算方法是等价的所以我们不需要枚举子集只需要简单的按照组合数进行计算就可以了。 具体的说我们把所有集合的元素都独立按方案二的选出来令\(f_i\)代表至少\(i\)个位置不选择元素的方案数则有 \[f_i\binom{n}{i}\prod\limits_{j1}^n \binom{a_jn-i-1}{n-i-1}\] 则总方案是 至少\(0\)人-至少\(1\)人...即 \[\sum_{i0}^{n-1}(-1)^if_i\] Code: #include cstdio
#define ll long long
const int N2000;
const ll mod1e97;
ll C[N10][N10];
void init()
{C[0][0]1;for(int i1;iN;i){C[i][0]1;for(int j1;ji;j)C[i][j](C[i-1][j]C[i-1][j-1])%mod;}
}
int n,m,a[N];ll ans;
int main()
{init();scanf(%d%d,n,m);for(int i1;im;i) scanf(%d,ai);for(int i0;in;i){ll mu1;for(int j1;jm;j)(mu*C[a[j]n-i-1][n-i-1])%mod;(ans(i1?-1ll:1ll)*C[n][i]*mu%mod)%mod;}printf(%lld\n,(ans%modmod)%mod);return 0;
} 2018.10.18 转载于:https://www.cnblogs.com/butterflydew/p/9808360.html
