题目部分

原题链接

题目描述

传说很久以前，大地上居住着一种神秘的生物：地精。

地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为N的山脉H可分为从左到右的N段，每段有一个独一无二的高度$H_i$，其中$H_i$是$1$到$N$之间的正整数。

如果一段山脉比所有与它相邻的山脉都高，则这段山脉是一个山峰。位于边缘的山脉只有一段相邻的山脉，其他都有两段（即左边和右边）。

类似地，如果一段山脉比所有它相邻的山脉都低，则这段山脉是一个山谷。

地精们有一个共同的爱好——饮酒，酒馆可以设立在山谷之中。地精的酒馆不论白天黑夜总是人声鼎沸，地精美酒的香味可以飘到方圆数里的地方。

地精还是一种非常警觉的生物，他们在每座山峰上都可以设立瞭望台，并轮流担当瞭望工作，以确保在第一时间得知外敌的入侵。

地精们希望这N段山脉每段都可以修建瞭望台或酒馆的其中之一，只有满足这个条件的整座山脉才可能有地精居住。

现在你希望知道，长度为N的可能有地精居住的山脉有多少种。两座山脉A和B不同当且仅当存在一个i，使得Ai≠Bi。由于这个数目可能很大，你只对它除以P的余数感兴趣。

输入格式

输入文仅含一行，两个正整数$N, P$。

输出格式

输出文件仅含一行，一个非负整数，表示你所求的答案对P取余之后的结果。

输入输出样例

输入 #1

4 7

输出 #1

3

数据范围

对于$20%$的数据，满足$N \leq 10$；

对于$40%$的数据，满足$ N \leq 18 $；

对于$70%$的数据，满足$ N \leq 550 $；

对于$100%$的数据，满足$ 3 \leq N \leq 4200，P \leq 1e9 $。

解题报告

题意理解

这道题目,让我们求出 波动序列 的总个数.
波动序列,感性理解即可,或者就是说,高度 上下起伏 的序列.

算法解析

这道题目,思维难度极大,但是代码难度极低,可以说是专门考思维的题目了.

首先,我们得在题目中,找到合适的性质,来求解本题.

第一个性质.

假如说,高度为$j$,和高度为$j-1$的山, 不相邻 的话,那么交换这两个山,依旧是合法的波动序列.

粗略证明.

我们知道,假如说$j$,所在的是山峰.

那么我们得出,身旁两个山, 最高 也是 $j-2$ $j-3$.

1. $j-1$和它不相邻
2. 山的高度是独一无二的.

因此我们把这个$j-1$移动过来,一定也可以构成山峰.

假如说$j-1$,所在的是山谷.
那么我们得出,对于$j-1$而言,两旁的山, 最矮 也是$j+1$,$j+2$

1. $j$和它不相邻
2. 山的高度是独一无二的

因此山谷还是山谷

那么假如说$j-1$所在的是山峰呢?

那么$j-1$而言,两旁的山,最高也就是 $j-2$,$j-3$.

1. $j$和它不相邻
2. 山的高度是独一无二的.

所以我们发现,这个山峰移动过来,同样还是山峰.

证明如上所示,对于$j$是山谷,同理可得,我们就不写了.

第二个性质

假如说现在的山们,高度分布为$[1,x]$,那么我们将所有的山,高度统统增加$1$

最后我们发现,波动序列不变.

证明:

因为高度关系没有改变,所以波动序列依旧波动.

只不过所有的山都长高了.

第三个性质

假如说$[1,x]$是一组波动序列,那么我们可以通过映射.

一个$[1,x]$的波动序列可以映射到一个$[y−x+1,y]$的波动序列.

你可以认为是所有高度相加$y-x$.

那么就是第二个性质的一个拓展了.

其实也就是所谓的,波动序列具有对称性质.

比如说:

$1 3 2 5 4$ 这是一个波动序列

那么

$4 5 2 3 1$ 同样也是一个波动序列.

方程推导

我们现在把所有的性质,都找出来了,那么接下来就是最难的推导过程了.

我们不妨,设置一下状态表示.

$f[i][j]表示[1,i]构成的排列中，第一个山峰,高度为j的波动序列的个数$

请注意,上面说是第一个山峰,不是第一个山谷,也就是说,这第一座山, 必须强制保证 为山峰.

现在我们思考一下,第二座山该放置情况.

假如说,第二座山不是$j-1$.

也就是说$j$,和$j-1$不是相邻的.

这说明什么?

我们可以使用第一个性质来转移.

因此我们不妨得出.

$$ f[i][j]+=f[i][j-1] $$

接下来,我们着重理解一下,第二三性质总和,得出的第二个推导方程.

我们之前分类讨论,讨论了,第二座山不是$j-1$的情况,那么接下来,我们着重分析.

第二座山就是$j-1$的情况.

此时,我们知道第二座山,必然是 山谷 了.

但是山谷的方案总数,其实和山峰的方案总数是一样的.

因为,每一个点,不是山谷就是山峰,确定了一个点是山谷,那么附近的点就是山峰.

确定了一座山的所属,那么其他山的所属也就确定了.

因此我们知道,$\text{山谷的方案数}=\text{山峰的方案数}$

因为第一座山已经确定了,那么后面的山一定在$[1,j−1] \cup [j+1,i]$这个范围内。

现在第二座山是$j-1$了,只不过是山谷,但是上面,我们证明了是$ \text{山谷总数}= \text{山峰总数} $

$$ f[i-1][j-1] 就是j-1在开头的山峰总数. $$

不过我们知道,山峰的前面都是山谷,山谷的前面都是山峰.

山谷山峰,交替出现.

所以不妨$[j+1,i] => [j,i-1]$

相当于从山谷,到了山峰.

而且因为性质二,我们知道,其实方案数量是没有变化的,因此相当于统统都$-1$了.

接下来通过,性质二变形得到的性质三,将这个$[j,i-1]$区间,映射到$[1,n]$开头的区间

这样离散化映射,就是为了,让我们统计出答案.

简而言之就是,所以山的高度,都减少$j-1$,那么这样的话,$[j,i-1]=>[1,(i-1)-(j-1)]$

这就是我们的区间离散化,得到的方案.

因此

$$ f[i][j]+=f[i-1][i-j] \\\\ i-j+1=(i-1)-(j-1) $$

记得使用滚动数组,使得内存在合适的范围

还有注意一下,根据波动序列具有对称性,所以最后答案要乘以2

代码解析

#include <bits/stdc++.h>
const int N=4210;
int n,p,f[2][N];
int main()
{
    scanf("%d%d",&n,&p);
    f[1][1]=1;
    for (int i=2; i<=n; ++i)
        for (int j=1; j<=i; ++j)
            f[i&1][j]=(f[i&1][j-1]+f[(i-1)&1][i-j])%p;
    printf("%d\n",f[n&1][n]*2%p);
}