地精部落

发表于 | 更新于
本文字数： 4k | 阅读时长 ≈ 4 分钟

地精部落

$Description$

$Solution$

神仙状态

设 $f_{i, j}$ 表示有 $i$ 个数，开头为 $j$ ，且 $j$ 为山峰的方案数。

首先要知道三个性质：
$$
对于一个满足条件的数列，其中的两个数\ i\ 与\ i + 1\ ，如果他们不相邻，交换他们的位置，这个数列仍然满足条件。
$$

$$
对于一个满足条件的数列，将数列中的每个数变为\ n + 1 - this\ ，这个数列的山峰与山谷情况相反，但仍然满足条件。
$$

$$
对于一个满足条件的数列，把这个数列顺序反一下，仍然满足条件。
$$

然后根据这三个性质，我们把一个数列分两类讨论。

我们把情况分成开头这个 $j$ 与 $j - 1$ 是否相邻来讨论。

对于两者不相邻的情况，根据性质一，我们发现直接交换两个数，把头换成 $j - 1$ 就可以得到一个新的合法的数列，所以可以通过 $f_{i, j - 1}$ 转移到。

对于两者相邻的情况，我们首先可知如果 $j$ 是山峰，那么 $j - 1$ 肯定是山谷，问题转化成有 $i - 1$ 个数，以 $j - 1$ 开头语，且 $j - 1$ 为山谷的方案数， 那么根据性质二，我们首先可以把这个数列转变成 $j - 1$ 为山峰的情况，即每个数变为 $n + 1 - this$ ，然后就可以通过 $f_{i - 1, i - j + 1}$ 转移到了。

所以最后的转移方程就是
$$
f_{i, j} = f_{i, j - 1} + f_{i - 1, i - j + 1}
$$

$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
//#include <tr1/unordered_map>
//#include"Bignum/bignum.h"
//#define lll bignum
#define ls(x) ( x << 1 )
#define rs(x) ( x << 1 | 1 )
#define mid ( (l + r) >> 1 )
#define lowbit(x) ( x & -x )
#define debug(x) (cout << "#x = " << (x) << endl)
#define Set(x, i) memset (x, i, sizeof(x))
#define R register
#define For(i, j, k) for(R int i = (j); i <= (k); ++i)
#define foR(i, j, k) for(R int i = (j); i >= (k); --i)
#define Cross(i, j, k) for(R int i = (j); i; i = (k))
using namespace std;
typedef long long ll;
const ll MAXN = 4211;
const ll INF = 5e16;

ll n, P, H[MAXN];

namespace IO {

    inline char gc() {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return (p1 == p2) && (p2 = (p1 = buf) +
            fread (buf, 1, 100000, stdin), p1 == p2)? EOF: *p1++;
    }

    #define dd ch = getchar()
    inline ll read() {
        ll x = 0; bool f = 0; char dd;
        for (; !isdigit (ch); dd) f ^= (ch == '-');
        for (; isdigit (ch); dd)  x = x * 10 + (ch ^ 48);
        return f? -x: x;
    }
    #undef dd

    inline void write( ll x ) {
        if (x < 0) putchar ('-'), x = -x;
        if (x > 9) write (x / 10); putchar (x % 10 | 48);
    }

    inline void wrn ( ll x ) { write (x); putchar (' '); }

    inline void wln ( ll x ) { write (x); putchar ('\n'); }

    inline void wlnn ( ll x, ll y ) { wrn (x), wln (y); }

}

using namespace IO;

namespace Subtask1 {

    ll Ans = 0, Vis[MAXN];
    
    inline void dfs ( ll pos, ll *H ) {
        if (pos == n + 1) return (void) (++Ans);
        For ( i, 1, n ) if (!Vis[i]) {
            if (pos < 2)
                Vis[i] = 1, H[pos] = i, 
                dfs (pos + 1, H), Vis[i] = 0, H[pos] = 0;
            else if (H[pos - 2] < H[pos - 1] && i < H[pos - 1]) 
                Vis[i] = 1, H[pos] = i, 
                dfs (pos + 1, H), Vis[i] = 0, H[pos] = 0;
            else if (H[pos - 2] > H[pos - 1] && i > H[pos - 1])
                Vis[i] = 1, H[pos] = i, 
                dfs (pos + 1, H), Vis[i] = 0, H[pos] = 0;
        }
    }

    void main () {
        if (n == 11) wln (707584 % P), exit (0);
        if (n == 12) wln (5405530 % P), exit (0);
        if (n == 13) wln (44736512 % P), exit (0);
        if (n == 14) wln (398721962 % P), exit (0);
        if (n == 15) wln (3807514624 % P), exit (0);
        dfs (1, H); wln (Ans * 2 % P); exit (0);
    }

}

namespace Subtask {
    
    ll f[3][MAXN];
    
    inline void main () {
        ll Ans = 0;
        f[0][2] = 1;
        For ( i, 3, n ) For ( j, 2, i ) 
            f[i & 1][j] = (f[i & 1][j - 1] + f[i - 1 & 1][i - j + 1]) % P;
        For ( i, 2, n ) Ans = (Ans + f[n & 1][i]) % P; wln (Ans * 2 % P); exit (0);
    }
    
}

int main()
{
//  freopen(".in", "r", stdin);
//  freopen("test.out", "w", stdout);
    n = read(), P = read();
    if (n <= 15) Subtask1::main (); 
    else Subtask::main (); return 0;
}

/*
707584
5405530
44736512
398721962
3807514624
*/

题目链接