江城唱晚

【题目背景】

墙角那株海棠，是你种下的思念。
生死不能忘，高烛照容颜。
一曲江城唱晚，重忆当年坐灯前，
青衫中绣着你留下的线。
——银临《江城唱晚》

【问题描述】

扶苏是个喜欢一边听古风歌一边写数学题的人，所以这道题其实是五三原题。
歌曲中的主人公看着墙边的海棠花，想起当年他其实和自己沿着墙边种了一排海
棠，但是如今都已枯萎，只剩下那一株，寄托着对他深深的思念。
沿着墙一共有$ n (个位置可以种下海棠花，主人公记得自己当年和他一共种下了) m
(朵，由于花的特性，海棠不能紧挨着种植，也就是两朵海棠花之间最少间隔一个不种花的空位置。但是她记不清当时海棠花具体是怎么摆放的了，所以她想知道一共有多少方案使得) m (朵海棠花都被种下且两两之间不是相邻的。我们将这) m $朵海棠花按照
$1,2,3…m (的顺序编号，两个种花的方案不同当且仅当它们被种下的位置不同或者从左向右数花的编号序列不同。为了避免输出过大，答案对一个参数) p $取模

【输入格式】

输入文件中有且仅有一组数据，只有一行四个数字，分别代表 (type,n,m,p)。其中
(type) 是一个帮助你判断测试点类型的参数，会在数据范围中说明。

【输出格式】

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

【输入输出样例】

$1 3 2 19260718 $

(2)

【输入输出样例解释】

一共有两朵花，3 个位置。如果给花朵编号为 1,2，位置编号为 1,2,3，那么两种
方案分别如下：
位置$ 1 2 3$
方案(1) 花朵$1space N/A $花朵(2)
方案(2) 花朵(2) $N/A $花朵(1)

【数据规模与约定】

子任务编号	n(leq)	m(leq)	type=	特殊性质	子任务分值
1	1	1	0	特殊性质1	5
2	20	20	1	特殊性质1	15
3	400	200	2	无	20
4	2000	1000	3	无	20
5	2000000	1000000	4	特殊性质2	20
6	2000000	1000000	5	无	20

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

特殊性质(2)：保证对应测试点的模数(p)是一个质数。定义整数(x)是一个质数当且仅当(x)有且只有(1)和(x)两个因数。

对于(100)%的数据，保证(1leq pleq 10^9)，(1leq mleq lceil frac{n}{2} ceil leq 10^6)，其中(lceil x ceil)为不小于(x)的最小整数。

【题解】

前言：(zay)神仙是把每一个子任务的方法都讲了一遍，这里主要讲(60)分的版本（(DP)）和(100)分的版本（组合数学）

(60)分思路：

首先设(f_{i,j})表示前(i)朵花按顺序种下，第(i)朵花种在第(j)个位置上的方案数。于是有(sum_{k=1}^{j-2}{f_{i,k}})，但是没有考虑花的序号，所以要再乘上(n!)。时间复杂度为(O(n^2m))显然只能过第三个子任务。

接下来考虑优化，我们可以用一个(G_{i,j})用来维护(sum_{k=1}^{j-2}{f_{i,k}})，则有(f_{i,j}=g{i,j-2})。于是复杂度降到(O(nm))。就不会出现这个结果了。但是也只能拿(60)分。

(100)分思路及代码：

考虑最后一个位置不种花的情况，这意味着每一朵花后面都跟了一个空位。我们将花和它后面的空位看成同一个物体，则问题变成了有$ (n-m) (个位置，放) m (个物体，放置无限制。根据组合数的定义，这样选位置的方案数为)C_{n-m}^{m}$。注意到这样仍然是不考虑花的序号的，要再乘上 (m!)。
考虑最后一个位置放花的情况，这意味着除了最后一朵花后面都跟了一个空位，我们去掉最后一个位置，剩下的花和后面的空位看成同一个物体，则同上可以计算方案数是(C_{n-m}^{m-1})。同样要乘上$ m!(。根据加法原理，总方案数为)$ m!(C_{n-m}^{m}+C_{n-m}{m-1}) $$。
由于模数是质数，预处理阶乘求一下阶乘逆元，即可做到(O(n log P))。但是只能过到第5个点。

如果你足够机智，可以发现上面的式子可以这么化：

$$m!(C_{n-m}^{m}+C_{n-m}{m-1})=m!C_{n-m}^{{m}+m!C_{n-m}}{m-1}=A_{n-m}^{m}+mA_{n-m}{m-1}$$

于是不用求逆元，直接求A即可。
当然，由于代数恒等式 (A_x^y+yA_x^{y-1}=A_{x+1}^y)，可以直接求(A_{n-m+1}^m) 。

这样就可以(A)了这道题了。