【洛谷 P5520】[yLOI2019] 青原樱 【组合数学】

[yLOI2019] 青原樱 【洛谷 P5520】

题目大意：

你有 $m$ 朵花，有 $n$ 个花盆，每朵花不能种在相邻的花盆中，每朵花都不一样 ，问你有多少种种植方案？

思路：

$m$ 朵花，$m-1$ 个空花盆，我们把 $m-1$ 抽出来扔掉，剩下的花不是随便种吗？
因为每一朵花都不一样，所以放的顺序不同会导致答案不同，那么我们用到的不是组合，而是排列。
答案就是 A n − ( m − 1 ) m = A n − m + 1 m = ( n − m + 1 ) ∗ ( n − m ) ∗ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ∗ ( n − 2 m + 3 ) ∗ ( n − 2 m + 2 ) A_{n-(m-1)}^{m}=A_{n-m+1}^{m}=(n-m+1)*(n-m)*······*(n-2m+3)*(n-2m+2) An−(m−1)m​=An−m+1m​=(n−m+1)∗(n−m)∗⋅⋅⋅⋅⋅⋅∗(n−2m+3)∗(n−2m+2)
时间复杂度$O(m)$

代码：

#include
#include
#include
#include
#include
#include
#include
#define r register
#define rep(i,x,y) for(r ll i=x;i<=y;++i)
#define per(i,x,y) for(r ll i=x;i>=y;--i)
using namespace std;
typedef long long ll;
const ll V=1e5+10;
ll opt,n,m,ans,p; 
inline ll in()
{ll res=0,f=1;char ch;while((ch=getchar())<'0'||ch>'9')if(ch=='-') f=-1;res=res*10+ch-48;while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;return res*f;
}
int main()
{opt=in();n=in(),m=in(),p=in();ans=1;ll x=n-m+1;rep(i,1,m){ans=(ans*x)%p;--x;}printf("%lld",ans); return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！