洛谷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;
}