#P5520. [yLOI2019] 青原樱

    ID: 4868 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划,dp数学2019算法O2优化组合数学排列组合

[yLOI2019] 青原樱

题目背景

星川之下皆萤火尘埃,
我独行在人潮你天真而待。
相遇若是借丹青着色,
青原上 绯樱如海。

——银临《青原樱》(Cover 人衣大人)

题目描述

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

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

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

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

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

输入格式

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

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

输出格式

输出一行一个整数,代表答案对 pp 取模的结果。

1 3 2 19260718
2

提示

样例输入输出 1 解释

一共有 22 个樱花幼苗, 33 个种花的位置,如果给幼苗编号为 1, 21,~2,位置编号为 1, 2, 31,~2,~3,那么两种方案分别如下:

位置 11 22 33
方案 1 幼苗 11 幼苗 22
方案 2 幼苗 22 幼苗 11

数据规模与约定

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

子任务编号 nn \leq mm \leq type=type= 特殊性质 子任务分值
1 11 00 特殊性质 1 55
2 2020 11 1515
3 400400 200200 22 2020
4 20002000 33
5 20000002000000 10000001000000 44 特殊性质 2
6 55

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

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

对于 100%100\% 的数据,保证:

  • 1n2×1061 \leq n \leq 2 \times 10^6
  • 1m1061 \leq m \leq 10^6
  • 1p1091 \leq p \leq 10^9
  • 1mn21 \leq m \leq \lceil\frac{n}{2} \rceil

提示

  • 请使用合适的数据类型来进行运算,避免溢出。
  • 参数 typetype 可以帮助你快速的判断子任务编号。