[Acwing] 第 60 场周赛 C-AcWing 4496. 吃水果

前言

t a g : tag : tag:组合数学 dp

传送门 :

题意 : 给定 n n n个人, m m m个水果,询问恰好有 k k k个人拿到的水果和左边的人不一样的方案数

组合思路 : 我们在 n − 1 n-1 n−1个人中挑选出 k k k个人

显然第一个人有 m m m种选法,那么剩下的要么是和第一个人相同要么就是不同

因此总共有 ( m − 1 ) k (m-1)^k (m−1)k种选法,而对应这 k k k个人又有 C n − 1 k C_{n-1}^k Cn−1k​种

所以总方案数 C n − 1 k ∗ m ∗ ( m − 1 ) k C_{n-1}^k*m*(m-1)^k Cn−1k​∗m∗(m−1)k

code :

ll qmi(ll a,ll b){
	ll res = 1;
	while(b){
		if(b&1) res = res*a%mod;
		a = a*a%mod;
		b>>=1;
	}
	return res;
}
ll f(ll x){
	ll res = 1;
	for(ll i=1;i>n>>m>>k;
	coutm>>k;
	for(int i=1;i