题解-JSOI2011 分特产

题面

JSOI2011 分特产

有 \(n\) 个不同的盒子和 \(m\) 种不同的球，第 \(i\) 种球有 \(a_i\) 个，用光所有球，求使每个盒子不空的方案数。

数据范围：\(1\le n,m,a_i\le 1000\)。

蒟蒻语

今天做了几道黑题，蒟蒻的做法非常蒟蒻，看上去很厉害其实很废，巨佬的做法是容斥，秒杀一切。

所以蒟蒻拿这道水题讲讲自己的做法。希望巨佬教蒟蒻容斥 \(\tt /kel\)。

蒟蒻解

看到盒子不能空，先二项式反演。

\(f(i)\) 表示 \(i\) 个盒子空，剩下非空的方案数；\(g(i)\) 表示 \(i\) 个盒子空，剩下随意。

\[g(i)=\sum_{x=i}^n {x\choose i}f(x)\Longleftrightarrow f(i)=\sum_{x=i}^n{x\choose i}(-1)^{x-i}g(x)
\]

然后考虑 \(g(i)\) 怎么求：因为 \(n-i\) 个可以空可以不空，所以可以构造生成函数：

\[\left(\prod_{j=1}^m(1+x_j+x_j^2+x_j^3+\cdots)\right)^{n-i}
\]

\(g(i)\) 就等于 \(\prod_{j=1}^mx_j^{a_j}\) 的项数。

所以可以每个 \(x_j\) 分开来考虑，用隔板法，得出：

\[g(i)={n\choose i}\prod_{j=1}^m{a_j+n-i-1\choose n-i-1}
\]

然后答案就是（当 \(x=n\) 时 \(n-x-1=-1\)，所以结果为 \(0\)，不需要枚举）：

\[f(0)=\sum_{x=0}^{n-1}(-1)^{x}{n\choose x}\prod_{j=1}^m{a_j+n-x-1\choose n-x-1}
\]

代码

跟巨佬的代码是一样的，只不过推导过程不同。

#include <bits/stdc++.h>

using namespace std;

//Start

typedef long long ll;

typedef double db;

#define mp(a,b) make_pair(a,b)

#define x first

#define y second

#define be(a) a.begin()

#define en(a) a.end()

#define sz(a) int((a).size())

#define pb(a) push_back(a)

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3f;

//Data

const int N=1e3,T=N<<1;

const int mod=1e9+7;

int n,m,a[N],c[T+1][T+1];

int g(int x){

    int res=c[n][x];

    for(int i=0;i<m;i++)

        res=(ll)res*c[a[i]+n-x-1][n-x-1]%mod;

    return res;

}

//Main

int main(){

    ios::sync_with_stdio(0);

    cin.tie(0),cout.tie(0);

    cin>>n>>m;

    for(int i=0;i<=T;i++){

        c[i][0]=c[i][i]=1;

        for(int j=1;j<=i-1;j++)

            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;

    }

    for(int i=0;i<m;i++) cin>>a[i];

    int ans=0;

    for(int i=0;i<n;i++){

        if(i&1) (ans+=mod-g(i))%=mod;

        else (ans+=g(i))%=mod;

    }

    cout<<ans<<'\n';

    return 0;

}

祝大家学习愉快！

巴特西

题解-JSOI2011 分特产

题面

蒟蒻语

蒟蒻解

代码

最新文章

热门文章