Luogu5505 JSOI2011分特产

2021-03-20 07:24

阅读：639

标签：== mes bin oid lin work dig int problem

Description

link

有 \(n\) 个同学和 \(m\) 种特产，要求分特产的时候不能有人没有特产

求方案数

\(n,m\le10^3\)

Solution

一道容斥的上手的题目吧

设我们不需要考虑没有特产的情况，直接上插板法统计答案

\[f(i)=\prod^{m} _ {i=1}\binom{a_i+n-1}{n-1} \]

然后我们考虑这个要减去有人没有特产的情况

首先删去有一个人没有特产的情况，就是分给 \(n-1\) 个人呗

这里我们发现如果直接 \(f_n-f_{n-1}\) 显然是个假的做法

因为由定义，这个 \(f_{n-1}\) 是有可能有\(n-2\)个人分到，\(1\)个人没有分到的

所以我们还得接着容斥

另：由于我们不知是哪 \(i\) 个人没有被分到，所以还是得乘上一个 \(\binom {n}{n-i}\)

Code

#include
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k==‘-‘) f=-1;
		while(isdigit(k)) res=res*10+k-‘0‘,k=getchar();
		return res*f;
	}
	const int N=3e3+10,mod=1e9+7;
	int inv[N],fac[N];
	inline void prework()
	{
		fac[0]=1; inv[0]=1; inv[1]=1;
		for(int i=1;i

Review

我们在解决容斥的题目的时候需要综合运用各种组合方法

同时精准找到重复信息然后进行枚举容斥

Luogu5505 JSOI2011分特产

标签：== mes bin oid lin work dig int problem

原文地址：https://www.cnblogs.com/yspm/p/12742055.html

上一篇：vue.js响应式原理解析与实现

下一篇：Ajax---错误处理

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Luogu5505 JSOI2011分特产
文章链接：http://soscw.com/index.php/essay/66594.html

亲，登录后才可以留言！

Luogu5505 JSOI2011分特产

Description

Solution

Code

Review

评论

热门文章

推荐文章

最新文章

置顶文章