洛谷题单指南-组合数学与计数-P5520 [yLOI2019] 青原樱

原题链接：https://www.luogu.com.cn/problem/P5520

题意解读：n个空位放1~m的数字，要求数字不能有相邻，求有多少种放法。

解题思路：

插空法：先确定n-m个不能放置数字的位置，这些位置的间隙包括两边形成n-m+1个空位，在这n-m+1个空位中选m个来放置1~m的数字，

一共有C(n-m+1, m)种选法，由于1~m的数字有顺序关系，总共是C(n-m+1, m) * m！种方法。

将组合式按定义展开得到：(n-m+1)!/(m-2m+1)!，即A(n-m+1,m)，直接做乘法求解即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N = 2e6 + 5;
LL type, n, m, p;int main()
{cin >> type >> n >> m >> p;LL ans = 1;for(int i = 0; i < m; i++){ans = ans * (n - m + 1 - i) % p;}cout << ans;return 0;
}