hdu 6397 Character Encoding 容斥

发布时间 2024-01-12 13:55:21作者: wljss

我是链接

刷刷计数防止大脑萎缩

题意:给定n,m,k,要求我们选m个范围在[0,n−1]中的数,使得这m个数的和为k

其中n,m,k都是10^5以内

如果没有范围在[0,n−1]的限制,就是小球与盒子经典例题,答案就是C(k+m-1,m-1)

有这个限制的话,考虑容斥,我们强制1个数不合法(其他的数也可能不合法,这一个数是必定不合法)的情况数为m*C(k+m-1-n,m-1),即拿出n放在这个数上,此时这个数必定不合法。

普遍来说,a个数不合法的情况数为C(m,a)C(k+m-1-an,m-1)

容斥下就行了