洛谷P5520 [yLOI2019] 青原樱 题解

题目链接：P5520 [yLOI2019] 青原樱

题意：

$n$ 个空放 $m$ 个物品，两两物品不能直接相邻，至少空一格

纯数学题。

看看几个空不能放，啊 $m-1$

那能放的就有 $n-m+1$ 个空

$$A_{n-m+1}^{m}$$

没了，水吧。直接算这个就好了。

为什么对呢，因为你在这 $n-m+1$ 个空里面可以随便放

时间复杂度 $O(n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

int n,m,p,_;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> _ >> n >> m >> p;
    int res=1;
    for(int i=n-m+1; i>=n-2*m+2; i--)
        res=res*i%p;
    cout << res << '\n';
    return 0;
}