【题解】青原樱
题目描述
扶苏是一个非常喜欢边听古风鸽边写数学题的人，因此这道题其实是个五三原题。
扶苏希望重现青原上樱花盛开的景色，于是他准备了很多互不相同樱花树幼苗，准备种成一行。
这一行中，一共有 n 个位置可以种下樱花，而扶苏准备了 m 支幼苗。由于樱花盛放时对左右空间需求非常大，所以樱花不能紧挨着种植，也就是任意两支幼苗之间必须至少存在一个不种花的空位置。
按照这种方式种花并不难，但是令扶苏感到好奇的是一共有多少合法的方案让他把这 m 支幼苗都种下去。一个方案是合法的当且仅当他满足上一段中叙述的要求。如果我们将花按照 1,2,3,…,m 编号，两种方案不同当且仅当被选择种花的位置不同或从左向右数花的编号序列不同。
为了避免输出过大，答案对一个参数 p 取模。
输入格式
每个输入文件中有且仅有一组测试数据。
测试数据只有一行四个整数，依次代表 type, n, m, p，其中 type 是一个帮助你判断测试点类型的参数，会在数据范围中说明。
输出格式
输出一行一个整数，代表答案对 p 取模的结果。
输入输出样例
输入 #1
1 3 2 19260718输出 #1
2说明/提示
样例输入输出 1 解释
一共有 2 个樱花幼苗， 3 个种花的位置，如果给幼苗编号为 1,~2，位置编号为 1,2,3，那么两种方案分别如下：
位置 | 1 | 2 | 3 |
|---|---|---|---|
方案 1 | 幼苗 1 | 空 | 幼苗 2 |
方案 2 | 幼苗 2 | 空 | 幼苗 1 |
数据规模与约定
本题采用多测试点捆绑测试，共有 6 个子任务。
子任务编号 | n≤n \leqn≤ | m≤m \leqm≤ | type=type=type= | 特殊性质 | 子任务分值 |
|---|---|---|---|---|---|
1 | 1 | 1 | 0 | 特殊性质 1 | 5 |
2 | 20 | 20 | 1 | 特殊性质 1 | 15 |
3 | 400 | 200 | 2 | 无 | 20 |
4 | 2000 | 2000 | 3 | 无 | 20 |
5 | 2000000 | 000000 | 4 | 特殊性质 2 | 20 |
6 | 2000000 | 1000000 | 5 | 无 | 20 |
特殊性质 1：保证对应测试点的实际方案数(在取模前)不超过 10610^6106
特殊性质 2：保证 p 是一个质数。
对于 100% 的数据，保证：
提示
- 请使用合适的数据类型来进行运算，避免溢出。
- 参数 type 可以帮助你快速的判断子任务编号。
题目分析
注意m个互不相同的幼苗需要不相邻地种植。这是一个组合数学中的不相邻问题。
不相邻问题插空处理。将n个不同的元素排成一排，其中k个元素互不相邻，求不同排法的步骤。
在本道题中，不能死搬硬套。首先，n个位置，樱花幼苗的编号是不同的，但是剩下的空余位置是相同的。所以不需要对第一步全排列。
问题变成了求从n−m+1个位置中挑选mmm 个的排列数，即
。
代码实现
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int main(){
ll t,n,m,p,ans=1;
cin>>t>>n>>m>>p;
n=n-m+1;
for(int i=n-m+1;i<=n;i++){//求A(n,m)
ans=ans*i%p;
}
cout<<ans%p;
return 0;
}Q.E.D.