题目大意

　　求在$[1,n]$的排列中是波动序列的数量。

题解

性质

　　当我们对波动序列$a$进行以下操作时，得到的新序列仍然是个波动序列：

若$a_i = a_j+1且|j-i|>1$，将$a_i,a_j$交换。
将波动序列上下翻转（也就是$\forall a_i, a_i\rightarrow n-a_i +1$）。
将波动序列左右翻转（也就是$\forall a_i, a_i\rightarrow a_{n-i+1}$）。

　　另外有性质1：对于任意一个长度为$n$，数值两两不同，且数值取值范围固定但不限于$[1,n]$的波动序列$a$，它的种类数与长度为$n$，数值取值等于$[1,n]$的序列的种类数是相同的。

状态的设计

　　由操作3我们可以想到：若我们规定每个波动序列的第一个数字都是山峰，那么最后我们的结果就是这些波动序列的数量*2，所以我们要用$j$表示第一个数字为$j$且它为山峰；因为一个波动序列的每一个子序列都满足性质1，所以我们要用$i$来表示波动序列长度为$i$，且数值取值范围等于$[1,i]$的结果。$f$表示这样的种类。状态$f(i,j)$就出来了。

状态的转移

　　由序列中元素$a_1$与$a_2$的关系分两种情况。

若$a_2<a_1-1$，对$a_1$该值操作1，得到$f(i,j-1)$。
若$a_2=a_1-1$，将子序列$[2,n]$内的元素由性质1可以对应到一个长度为$i-1$取值范围等于$[1,i-1]$的波动序列，将该序列进行操作2，得到$f(i-1,i-j+1)$

　　所以最后的递推式为$f(i,j)=f(i,j-1)+f(i-1,i-j+1)$

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define F(i, j) Dp[(i) & 1][j]

const int MAX_N = 5000;

long long Dp[2][MAX_N], P;

int N;

long long DP()

{

	F(2, 2) = 1;

	for (int i = 3; i <= N; i++)

	{

		memset(Dp[i & 1], 0, sizeof(Dp[i & 1]));

		for (int j = 2; j <= i; j++)

			F(i, j) = (F(i, j - 1) + F(i - 1, i - j + 1)) % P;

	}

	long long ans = 0;

	for (int i = 2; i <= N; i++)

		ans = (ans + F(N, i)) % P;

	return (ans * 2) % P;

}

int main()

{

#ifdef _DEBUG

	freopen("c:\\noi\\source\\input.txt", "r", stdin);

#endif

	scanf("%d%lld", &N, &P);

	printf("%lld\n", DP());

	return 0;

}

巴特西

luogu2467 [SDOI2010]地精部落

题目大意

题解

性质

状态的设计

状态的转移

最新文章

热门文章