洛谷P5520 【[yLOI2019] 青原樱】

这题是小学奥数啊。

题意：求\(m\)个不同物品两两不相邻的方案数。

直接排列组合。

我们可以减掉他们之间最少需要空出来的位数——\(m-1\)个空位

像这样，我们只用留\(m-1\)个空位放在每两个物品中间使他们两两不相邻即可。

所以剩下的位置有\(n-m+1\)个空位。

这个问题就转换成了一下这个问题：

给定\(n-m+1\)个位子，放入m个不同物品的方案数。

直接排列一下就好了。

\(ans\)=\(A_{n-m+1}^{m}\)

#include<bits/stdc++.h>

using namespace std;

int type,n,m,mod,cnt;

long long ans=1;

int main()

{

	scanf("%d%d%d%d",&type,&n,&m,&mod);

	for(int i=n-m+1;i>=n-2*m+2;i--)

	{

		ans=(ans*i)%mod;

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

洛谷P5520 【[yLOI2019] 青原樱】

最新文章

热门文章