【题解】分特产

题意：
有m种物品，每个物品有ar[i]个，将其分予n人使得每人至少有一个，求分配方法种数。

容斥原理。
运用容斥原理关键在于求得至多或至少然后去重。题目中有一个“至少”，不过显然不是我们要找的。
不妨这样理解：每人至少有一个，也就是有0人没有被分到。那么我们可以找至少有x人没被分到，容斥一下便是0人没被分到的结果。
考虑至少有x人没有被分到：C(n,x)选出x人，插板法将每种物品分给剩下的n-x人，每个人被分到的可以为零，乘法原理相乘即可：f(x)=C(n,x)* $图片说明$ C(ar[i]+n-i-1,n-i-1)。
所以答案即为f(0)-f(1)+f(2)-...+ $图片说明$ * f(m-1)。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=1e3+9;
const ll maxx=1e4+9;

int n,m,ar[maxn];
ll fac[maxx]={1,1},inv[maxx]={1,1};

inline ll qpow(ll x,ll t)
{
    ll res=1;
    while(t)
    {
        if(t&1) res=(res*x)%mol;
        t>>=1; x=(x*x)%mol;
    }
    return res;
}
void init()
{
    for(ll i=2;i<maxx;i++)
    {
        fac[i]=fac[i-1]*i%mol;
        inv[i]=qpow(fac[i],mol-2)%mol;
    }
}
inline ll c(ll n,ll r)
{
    if(r==0||r==n) return 1;
    if(r<0||r>n) return 0;
    return fac[n]*inv[r]%mol*inv[n-r]%mol;
}
inline ll cal(int t)
{
    ll res=1;
    for(int i=0;i<m;i++)
        res=res*c(ar[i]+n-t-1,n-t-1)%mol;
    return res;
}
int main()
{
    init();
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++) scanf("%d",&ar[i]);
    ll res=0,C=1;
    for(int i=0;i<n;i++)
    {
        res=(res+C*cal(i)%mol+mol)%mol;
        C=(n-i)*C%mol*qpow(i+1,mol-2)%mol*(-1);
    }
    printf("%lld\n",res);
}

【题解】 分特产

【题解】分特产