题解：P5520 [yLOI2019] 青原樱

P5520 [yLOI2019] 青原樱

题目

这一行中，一共有 个位置可以种下樱花，而扶苏准备了 支幼苗。由于樱花盛放时对左右空间需求非常大，所以樱花不能紧挨着种植，也就是任意两支幼苗之间必须至少存在一个不种花的空位置。

按照这种方式种花并不难，但是令扶苏感到好奇的是一共有多少合法的方案让他把这 支幼苗都种下去。一个方案是合法的当且仅当他满足上一段中叙述的要求。如果我们将花按照 编号，两种方案不同当且仅当被选择种花的位置不同或从左向右数花的编号序列不同。

为了避免输出过大，答案对一个参数 取模。

测试数据只有一行四个整数，依次代表 $type,n,m,~ptype$ 是一个帮助你判断测试点类型的参数，会在数据范围中说明。

说明/提示

数据规模与约定

本题采用多测试点捆绑测试，共有 6 个子任务。

子任务编号				特殊性质	子任务分值
1				特殊性质 1
2				特殊性质 1
3				无
4				无
5				特殊性质 2
6				无

特殊性质 1：保证对应测试点的实际方案数(在取模前)不超过

特殊性质 2：保证 是一个质数。

对于 的数据，保证：

• 。
• 。
• 。
• 。

题解

考虑先确定填空位置，再计算填空顺序，答案 = 填空位置方案数 × 树苗全排列；

• 填空位置方案数，使用隔板法 ；
• 已经确定的部分是 个物品以及它们之间的 个空位；
• 考虑 个余位填入 个隔板缝隙（含两端）；

方案数：

• 发现直接这么整是不行的，因为 不一定是质数。
• 注意到一个细节：我们把式子展开：

噫！好了！不用除法了！不用模数为质数了！

代码

#include<bits/stdc++.h>
using namespace std;
int t, n, m, p;
long long ans = 1;
int main() {
    scanf("%d%d%d%d", &t, &n, &m, &p);
    for (int i = (n - 2 * m + 2); i <= (n - m + 1); ++i)
        ans = (ans * i) % p;
    cout << ans;
    return 0;
}

延伸（至少空 格）

若改成“相邻幼苗之间至少空 个位置”，同理令 ，则

其中需要 才有解。