题目描述

扶苏是一个非常喜欢边听古风鸽边写数学题的人，因此这道题其实是个五三原题。

扶苏希望重现青原上樱花盛开的景色，于是他准备了很多互不相同樱花树幼苗，准备种成一行。

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

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

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

输入格式

每个输入文件中有且仅有一组测试数据。

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

输出格式

输出一行一个整数，代表答案对 $p$ 取模的结果。

数据规模与约定

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

子任务编号	$n \leq$	$m \leq$	$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$	$1000000$	$4$	特殊性质 2	$20$
6	$2000000$	$1000000$	$5$	无	$20$

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

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

对于 $100\%$ 的数据，保证：

• $1 \leq n \leq 2 \times 10^6$。
• $1 \leq m \leq 10^6$。
• $1 \leq p \leq 10^9$。
• $1 \leq m \leq \lceil\frac{n}{2} \rceil$。

前置知识

插空法

插空法一般用于处理某些元素不相邻的问题。

在解决对于某几个元素要求不相邻的问题时，我们可以先将其它元素（可以相邻的元素）排好，然后再将指定的不能相邻的元素插入已排好元素的间隙或两端位置，从而解决问题。

解题思路

简要题意：一共有 $n$ 个位置，$m$ 棵不同的树，两棵树不能相邻（即两棵树之间要有空位）。

可以先把 $m$ 棵树以及他们所在的位置从 $n$ 个位置中取出来，于是剩下的空位有 $n-m+1$ 个，我们要把带着坑的树重新栽种在这 $n-m+1$ 个空位中，那么一共有 $A^m_{n-m+1}$ 种方案。

由于树都是不同的，带有顺序，所以是 $A$ 而不是 $C$。

正确代码

写的时候注意一下数据范围，计算过程可能会爆 $int$。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int type, n, m, p;

int A(int n, int m)
{
	int res = 1;
	for (int i = n - m + 1; i <= n; i ++ )
		res = (ll)res * i % p;
	return res;
}

int main()
{
	cin >> type >> n >> m >> p;
	cout << A(n - m + 1, m) << endl;
	return 0;
}