[题解] [bzoj4710] 分特产

题面

题解

如果没有每个人都分的限制, 直接上组合数即可

考虑容斥

设\(f[i]\)为至少有\(i\)个人没有分到特产的方案, 我们可以知道
\[ \displaystyle f[i] = \binom{n}{i}\prod_{j = 1}^{m}\binom{a_j+n-1-i}{n-1-i} \]
其中\(a_j\)为第\(j\)种特产的数量
\[ \displaystyle \binom{n}{m} = C_n^m \]
解释一下上面的东西吧, 首先从\(n\)个数中选出\(i\)个数代表不选, 然后对于每一种特产, 相当于拿\(n - 1 - i\)块隔板插入将这\(a_j\)个特产分为\(n - i\)块, 注意到其中有一些块是可以为空的, 我们新建\(n - 1 - i\)个点, 要是选了这些点中的第\(i\)个点就代表第\(i\)块为空, 所以最后就是
\[ \displaystyle \prod_{j = 1}^{m}\binom{a_j+n-1-i}{n-1-i} \]
实在不懂就去百度插板法详解吧, 这只是一篇题解, 我不会讲得太详细

然后容斥系数是
\[ \displaystyle (-1)^i \]
各位画个韦恩图就知道了

所以, 最后的答案是
\[ ans = \sum_{i = 0}^{n}(-1)^if[i] \]

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#define itn int
#define reaD read
#define N 2005
#define mod 1000000007
using namespace std;

int n, m, a[N], c[N][N];
long long ans = 0; 

inline int read()
{
    int x = 0, w = 1; char c = getchar();
    while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * w;
}

int main()
{
    n = reaD(); m = read(); 
    for(int i = 1; i <= m; i++) a[i] = read();
    for(int i = 0; i <= 2000; i++)
    {
        c[i][0] = 1; 
        for(int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod; 
    }
    for(int i = 0; i <= n; i++)
    {
        long long res = i & 1 ? mod - 1 : 1; res = 1ll * res * c[n][i] % mod; 
        for(int j = 1; j <= m; j++) res = 1ll * res * c[n + a[j] - 1 - i][n - 1 - i] % mod;
        ans = (ans + res) % mod; 
    }
    printf("%lld\n", ans); 
    return 0;
} 

[题解] [bzoj4710] 分特产

原文：https://www.cnblogs.com/ztlztl/p/11181876.html