BZOJ1925或洛谷2467 [SDOI2010]地精部落

时间:2022-01-04 15:24:32

BZOJ原题链接

洛谷原题链接

先讲下关于波动数列的\(3\)个性质。

性质\(1\):对于数列中的每一对\(i\)和\(i + 1\),若它们不相邻,那么交换这两个数形成的依旧是一个波动数列。

性质\(2\):对于任何一个由\(1\sim n\)组成的波动数列,将每个数\(a_i\)变为\(n + 1 - a_i\),形成的依旧是波动数列,且山峰和山谷与原先的数列刚好相反。

性质\(3\):波动数列有对称性,即一个波动数列倒过来依旧是波动数列。

由性质\(3\),我们可以只考虑第一个数为山峰的情况,最后将答案\(\times 2\)即可(如果\(n = 1\)是需要特判的,但这题保证\(n \geqslant 3\),所以无所谓)。

设\(f[i][j]\)表示由\(1 \sim i\)组成、首位为\(j\)(且为山峰)的波动数列方案数。

则有状态转移方程:

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

解释下这个转移方程。

  1. 若\(j\)与\(j - 1\)不相邻,那么产生的方案数就是\(f[i][j - 1]\)。

    因为当\(j - 1\)为首位且为山峰,那么\(j\)显然不可能和它相邻,即不可能在次位,否则\(j\)就成山谷了,所以根据性质\(1\),\(j - 1\)在首位的方案数即是\(j\)在首位且与\(j - 1\)不相邻的方案数。
  2. 若\(j\)与\(j - 1\)相邻,那么产生的方案数就是\(f[i - 1][i - j + 1]\)。

    因为此时的数列是\(j,j - 1,\dots\)的形式,那么这时的方案数就相当于给你\([1,j - 1]\cup[j + 1, i]\)的数,求\(j - 1\)在首位且为山谷的方案数,由于我们在考虑的数的大小均是相对的,所以给你\([j +1,i]\)等同于给你\([j, i - 1]\)的数,所以就转换为由\(1 \sim i - 1\)组成的波动数列,求\(j - 1\)在首位且为山谷的方案数,根据性质\(2\),这个问题就等同于由\(1 \sim i - 1\)组成的波动数列,求\((i - 1) + 1 - (j - 1) = i - j + 1\)在首位且为山峰的方案数,即\(f[i - 1][i - j + 1]\)。

最后的答案即为\(2 \times \sum \limits _{i = 2} ^ n f[n][i]\),因为\(1\)在首位不可能为山峰,所以从\(2\)开始累计。

代码里我使用了滚动数组来缩小空间。

#include<cstdio>
using namespace std;
const int N = 4210;
int f[2][N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
int main()
{
int i, j, n, p, s = 0;
n = re();
p = re();
f[0][2] = 1;
for (i = 3; i <= n; i++)
for (j = 2; j <= i; j++)
f[i & 1][j] = (1LL * f[i & 1][j - 1] + f[(i & 1) ^ 1][i - j + 1]) % p;
for (i = 2; i <= n; i++)
s = (1LL * s + f[n & 1][i]) % p;
printf("%lld", 2LL * s % p);
return 0;
}