推荐题目：洛谷 P5520 [yLOI2019] 青原樱

推荐题目洛谷P5520 [yLOI2019] 青原樱题目背景星川之下皆萤火尘埃我独行在人潮你天真而待。相遇若是借丹青着色青原上 绯樱如海。——银临《青原樱》(Cover 人衣大人)题目描述扶苏是一个非常喜欢边听古风鸽边写数学题的人因此这道题其实是个五三原题。扶苏希望重现青原上樱花盛开的景色于是他准备了很多互不相同樱花树幼苗准备种成一行。这一行中一共有n nn个位置可以种下樱花而扶苏准备了m mm支幼苗。由于樱花盛放时对左右空间需求非常大所以樱花不能紧挨着种植也就是任意两支幼苗之间必须至少存在一个不种花的空位置。按照这种方式种花并不难但是令扶苏感到好奇的是一共有多少合法的方案让他把这m mm支幼苗都种下去。一个方案是合法的当且仅当他满足上一段中叙述的要求。如果我们将花按照1 , 2 , 3 , … , m 1,2,3,\dots,m1,2,3,…,m编号两种方案不同当且仅当被选择种花的位置不同或从左向右数花的编号序列不同。为了避免输出过大答案对一个参数p pp取模。输入格式每个输入文件中有且仅有一组测试数据。测试数据只有一行四个整数依次代表t y p e , n , m , p type,~n,~m,~ptype,n,m,p其中t y p e typetype是一个帮助你判断测试点类型的参数会在数据范围中说明。输出格式输出一行一个整数代表答案对p pp取模的结果。输入输出样例 #1输入 #11 3 2 19260718输出 #12说明/提示样例输入输出 1 解释一共有2 22个樱花幼苗3 33个种花的位置如果给幼苗编号为1 , 2 1,~21,2位置编号为1 , 2 , 3 1,~2,~31,2,3那么两种方案分别如下位置1 112 223 33方案 1幼苗1 11空幼苗2 22方案 2幼苗2 22空幼苗1 11数据规模与约定本题采用多测试点捆绑测试共有 6 个子任务。子任务编号n ≤ n \leqn≤m ≤ m \leqm≤t y p e typetype特殊性质子任务分值11 111 110 00特殊性质 15 55220 202020 20201 11特殊性质 115 15153400 400400200 2002002 22无20 202042000 200020002000 200020003 33无20 202052000000 200000020000001000000 100000010000004 44特殊性质 220 202062000000 200000020000001000000 100000010000005 55无20 2020特殊性质 1保证对应测试点的实际方案数(在取模前)不超过10 6 10^6106特殊性质 2保证p pp是一个质数。对于100 % 100\%100%的数据保证1 ≤ n ≤ 2 × 10 6 1 \leq n \leq 2 \times 10^61≤n≤2×106。$1 \leq m \leq 10^6 $。1 ≤ p ≤ 10 9 1 \leq p \leq 10^91≤p≤109。1 ≤ m ≤ ⌈ n 2 ⌉ 1 \leq m \leq \lceil\frac{n}{2} \rceil1≤m≤⌈2n​⌉。提示请使用合适的数据类型来进行运算避免溢出。参数t y p e typetype可以帮助你快速的判断子任务编号。