当前位置：网站首页>[Acwing] 第 60 场周赛 C-AcWing 4496. 吃水果

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

2022-07-17 12:39:00 【*DDL_GzmBlog】

前言

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<=x;i++) res = res*i%mod;
	return res%mod;
}
ll inv(ll x){
    
	return qmi(x,mod-2);
}
ll getC(ll a,ll b){
    
	return f(a)*inv(f(a-b)*f(b)%mod)%mod;
}
void solve(){
    
	cin>>n>>m>>k;
	cout<<(getC(n-1,k)*m%mod)*qmi(m-1,k)%mod<<endl;
}

dp思路 :
我们设状态
d p [ i ] [ j ] 表示前 i 位有 j 个不同的方案数 dp[i][j]表示前i位有j个不同的方案数 dp[i][j]表示前i位有j个不同的方案数

那么转移很好想到
d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i − 1 ] [ j − 1 ] ∗ ( m − 1 ) dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(m-1) dp[i][j]=dp[i−1][j]+dp[i−1][j−1]∗(m−1)

(前面已经凑出来 j j j个不同 d p [ i − 1 ] [ k ] dp[i-1][k] dp[i−1][k]
(前面只凑出来 j − 1 j-1 j−1个不同,因此当前的选择需要乘上 ( m − 1 ) (m-1) (m−1)

code :

ll dp[N][N];
ll n,m,k;
void solve(){
    
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++) dp[1][i] = 0 ;
	//第一个不算
	for(int i=1;i<=n;i++) dp[i][0]=m;
	
	for(int i=2;i<=n;i++)
		for(int j=1;j<=k;j++)
		dp[i][j] = (dp[i-1][j]+dp[i-1][j-1]*(m-1)%mod)%mod;

	cout<<dp[n][k]<<endl;
}
原网站

版权声明
本文为[*DDL_GzmBlog]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_34364611/article/details/125824137

边栏推荐

猜你喜欢

随机推荐