HDU5201-The Monkey King

题目

题目大意

简化题意：1~n个不同盒子，放入m个相同小球，盒子可空，但是1号盒子的球数必须严格最多，问合法方案数。

分析

简化问题

如果没有1号盒子严格最多的限制，就变成了一个插板的问题。

也就是$x_1+x_2……+x_n=m$x1​+x2​……+xn​=m这类不定方程求非负整数解的问题，插板法解决。

容斥

如果枚举猴王（1号盒子）的球数为i

那么问题就变成不定方程并且$0<=x<=i$0<=x<=i，加了一个上限。

上限通常会用容斥转化成下限，下限继续插板解决。

枚举至少k个盒子的球数$>=i$>=i，然后容斥解决问题。

假设现在是要求至少k个盒子的球数不少于1号盒子，那么就先选出k个盒子，也就是$C_{m-1}^{k}$Cm−1k​

然后向每个选出来的盒子放i个球，剩下的$n-(k+1)*i$n−(k+1)∗i个球随便放入$m-1$m−1个盒子里面

然后运用插板法，$C_{n-(k+1)*i+m-2}^{m-2}$Cn−(k+1)∗i+m−2m−2​种方法。

子问题得证

现在我们解决了已知1号盒子球数i、至少k个盒子的球数不小于i的方案个数。

然后就用容斥解决。

容斥其实和二项式反演有关，有的时候容斥不太好理解或者好想到，就先想到二项式反演再得到容斥的式子。

这里就先给出容斥的形式，二项式反演后文会讲解。

确定i的时候，令$f(k)$f(k)表示至少k个盒子球数不少于i的方案数

$f(k)=C_{m-1}^{k}*C_{n-(k+1)*i+m-2}^{m-2}$f(k)=Cm−1k​∗Cn−(k+1)∗i+m−2m−2​

那么对于i，答案为：$\sum_{k=0}^{n-(k+1)*i>=0} {(-1)^{k}f(k)}$∑k=0n−(k+1)∗i>=0​(−1)kf(k)

相关代码

for(int i=1;i<=n;i++){//枚举猴王得到的桃子个数 
			long long id=1;
			for(int k=0;n-(k+1)*i>=0;k++){//枚举至少有k只小猴子得到的桃子个数>猴王 
				ans+=id*C(m-1,k)%mod*C(n-(k+1)*i+m-2,m-2)%mod;
				ans%=mod;
				id=-id;
			}
		}

代码

下附AC代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int read(){
	char s;
	int x=0,f=1;
	s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-')f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9'){
		x*=10;
		x+=s-'0';
		s=getchar();
	}
	return x*f;
}
const long long mod=1000000007;
const int N=300000;
long long qpow(long long a,long long b){
	if(b==0)return 1;
	long long rec=qpow(a,b/2)%mod;
	if(b&1)return rec*rec%mod*a%mod;
	return rec*rec%mod;
}
long long calc[N],inv[N];//阶乘 阶乘逆元 
void init(int n){
	calc[0]=1;
	for(long long i=1;i<=n;i++){
		calc[i]=calc[i-1]*i%mod;
	}
	inv[n]=qpow(calc[n],mod-2);
	for(long long i=n-1;i>=0;i--){
		inv[i]=inv[i+1]*(i+1)%mod;
	}
	return;
}
long long C(int a,int b){//组合数 
	if(b>a)return 0;
	return calc[a]*inv[b]%mod*inv[a-b]%mod;
}
int main(){
	int T=read();
	init(N-5);
	while(T--){
		int n,m;
		n=read(),m=read();//n个桃子，m个猴子 
		if(m==1||n==1){
			puts("1");
			continue;
		}
		long long ans=0;
		for(int i=1;i<=n;i++){//枚举猴王得到的桃子个数 
			long long id=1;
			for(int k=0;n-(k+1)*i>=0;k++){//枚举至少有k只小猴子得到的桃子个数>猴王 
				ans+=id*C(m-1,k)%mod*C(n-(k+1)*i+m-2,m-2)%mod;
				ans%=mod;
				id=-id;
			}
		}
		ans=(ans%mod+mod)%mod;
		printf("%lld\n",ans);
	}
}

相关知识

这道题挺综合的，考了很多组合基本知识

插板法介绍

插板法是解决这么一类问题：不定方程$x_1+x_2……+x_n=m$x1​+x2​……+xn​=m的非负整数解的问题

其中mn为正整数

我们把题目转化成求正整数解，也就是每个数先+1：

$x_1+1+x_2+1……+x_n+1=m+n$x1​+1+x2​+1……+xn​+1=m+n

令$x_i=x_i+1$xi​=xi​+1

这样取值范围也向上加一

那我们把它看成，m+n个相同小球，分成非空的n堆，这样从左往右n堆分别代表n个x，这就把解转化为划分方式（注意，与第二类斯特林数不同，这个盒子是相同的，没学过的直接忽略这句话）

那么由于现在是非空的，就有了$m+n-1$m+n−1个空隙，插入$n-1$n−1个板子，就是组合数$C_{m+n-1}^{n-1}$Cm+n−1n−1​了

这就是插板法解决不定方程问题。

二项式反演介绍

具体内容见：二项式反演

那么这道题怎么用二项式反演呢？

其实前面的从$m-1$m−1个盒子里面选$k$k个盒子，就蕴含了二项式反演。

当ik确定的时候（一号盒子有i个球，后m-1个盒子里有k个盒子球数不少于i）

我们令$f(k)$f(k)表示恰好k个盒子的球数不少于i

$g(k)$g(k)表示至少k个盒子球数不少于i

那么这里的g函数就和容斥的f函数不一样了。

我就需要钦点k个盒子而不是*排列组合选出k个盒子。

我钦点了前k个也就是$2····{k+1}$2⋅⋅⋅⋅k+1这几个盒子每个先放进去i个球，然后剩下的插板解决。

这样才能保证g函数表示至少k个盒子而不会算重。

$g(k)=C_{n-(k+1)*i+m-2}^{m-2}$g(k)=Cn−(k+1)∗i+m−2m−2​

$g(k)=\sum_{j=k}^{m-1}{C_{m-1}^{j}f(j)}$g(k)=∑j=km−1​Cm−1j​f(j)

为什么要乘组合数呢？

我们来看：

画个图辅助理解：我们看蓝色点，表示恰好3个。那么绿、黄、红都代表至少两个。

那么在f函数里面，恰好3个的一种方案：蓝色点，在至少两个里面出现了三次。

因为我们回到“至少”函数$g$g的推导：我们钦点一部分作为一开始各分发i个小球的，剩下球随便给，黄绿红分别代表钦点的方案，剩下的一个点代表随便给球出现的，那么一个蓝色就对应了三种“至少”方案。

因此，可以得到上面的表达式。

那么上面那个表达式代入二项式反演得到容斥的那个式子：

$\sum_{k=0}^{n-(k+1)*i>=0} {(-1)^{k}C_{m-1}^{k}*C_{n-(k+1)*i+m-2}^{m-2}}$∑k=0n−(k+1)∗i>=0​(−1)kCm−1k​∗Cn−(k+1)∗i+m−2m−2​

小总结

其实发现二项式反演和容斥的最终结果完全一样。

容斥选择至少k个不小于i的盒子直接用组合选。

但是二项式反演要钦点前k个，然后在“至少”和“恰好”之间转化的时候加上第一个组合数。

看似多此一举，实则在以后的难题里运用更广泛。

总结

这道题不失为一道组合好题

它综合运用多种知识，并不难。

这道题用二项式反演其实大材小用了，网上做法很多都是直接容斥。

但是以后遇到更难的题目的时候，想想二项式反演来辅助得到容斥结果也未尝不可。

推荐题目：已经没有什么好害怕的了

附带此题题解：题解

谢谢观看，敬请指正。