LOJ3276

Solution

aia_i为给出的数组,bib_i为最终状态的数组,在DP时要注意区分这两个概念

首先考虑若给出aia_i,判断是否满足条件

仔细理解题意后发现最终状态可以按如下方式得到: 从后往前考虑每个aia_i,若存在一个最大的xx满足1xai1 \le x \le a_ixx还未被标记,那么bib_i就等于xx,然后把xx标记

考虑DP,设f(i,j)f(i, j)表示考虑了ii2n2n个石柱,且在最终状态中已经存在高度为 的石柱,考虑从f(i+1,j)f(i +_ 1, j)ii转移

cnt0cnt0表示[i+1,2n][i + 1, 2n]中,bi=0b_i = 0的数的个数,cnt1cnt1表示[i+1,2n][i + 1, 2n]中,bi>0b_i > 0的数的个数

  1. bi=0b_i = 0,则aia_i应填入j\le j的数

    不难发现j\le j的数恰好被填入了j+cnt0j + cnt0个。然而根据状态的定义,我们不能确定那cnt0cnt0个数到底是哪几个。于是考虑放宽限制,将aia_i中高度相同的两个数也视为不同(看成有标号的),并将最终答案除掉2n2 ^ n

    那么此时bib_i就有jcnt0j - cnt0种填法

  2. bi>0b_i > 0,则aia_i应填入>j> j的数。考虑先确定bib_i填什么

    • bij+1b_i \ne j + 1,可以考虑暂时不填aia_i (因为对状态没有影响,等到j+1j + 1被填的时候再考虑它怎么填)

    • 否则,枚举kk表示填入aia_i后,最终状态中已经存在高度

      先用组合数把后k1k - 1个元素的位置选出来:(cnt1jk1)\displaystyle \binom{cnt1 - j}{k - 1},然后考虑aia_i可以填什么

      因为新填入的后k1k - 1个元素在最终状态中一定是 ,所以aia_ik+1k + 1种可能的填法,分别是:(j+1),(j+1)(j + 1), (j + 1)'这两个数,以及取值在 中的k1k - 1个数

      关于这部分我不太知道要怎么表述。。。就举个例子吧:

      假设当前j=0,k=4j = 0, k = 4,那后面的aia_i可能是: 2,3,42', 3, 4',那当前位置的aia_i就能填1,1,2,3,41, 1', 2, 3', 455个数

      而后面的aa还有可能是2,4,42, 4, 4',这样得到的bb也是合法的,那当前位置的aia_i就能填1,1,2,3,31, 1', 2', 3, 3',还是55个数

      于是有转移方程:

      f(i,j+k)f(i+1,j)×(cnt1jk1)×coefk1×(k+1) f(i, j + k) \leftarrow f(i + 1, j) \times \binom{cnt1 - j}{k - 1} \times coef_{k - 1} \times (k + 1)

      其中coeficoef_{i}表示从i\le i的这2i2i个数中选出ii个数作为aa,得到的bb恰好为 的方案数

      考虑设g(i,j)g(i, j)表示从i\le i的数中选出jj个数,使其合法的方案数,那么有:

      g(i,j)=g(i1,j)+g(i1,j1)×2j+g(i1,j2)×j(j1) g(i, j) = g(i - 1, j) + g(i - 1, j - 1) \times 2j + g(i - 1, j - 2) \times j(j - 1) coefi=g(i,i) coef_i = g(i, i)

时间复杂度O(n3)O(n^3)

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch - '0');
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 600 * 2;
const int MOD = 1e9 + 7;

namespace MATH
{
int fac[MAXN + 5], ifac[MAXN + 5], inv[MAXN + 5];

inline void ADD (int &a, int b) { if ((a += b) >= MOD) a -= MOD; }

inline int Pow (int a, int b)
{
int ans = 1;
for (int i = b; i; i >>= 1, a = (LL) a * a % MOD) if (i & 1) ans = (LL) ans * a % MOD;
return ans;
}

inline void init (int n = MAXN + 1)
{
fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = (LL) fac[i - 1] * i % MOD;
ifac[n] = Pow (fac[n], MOD - 2); for (int i = n - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % MOD;
for (int i = 0; i < n; ++i) inv[i + 1] = (LL) fac[i] * ifac[i + 1] % MOD;
}

inline int C (int n, int m) { if (n < m || n < 0 || m < 0) return 0; return (LL) fac[n] * ifac[m] % MOD * ifac[n - m] % MOD; }
}

using namespace MATH;

int N, is_key[MAXN + 5];
int coef[MAXN + 5][MAXN + 5];
int F[MAXN + 5][MAXN + 5];

inline void Init ()
{
for (int i = 0; i <= N; ++i)
{
coef[i][0] = 1;
for (int j = 1; j <= i; ++j)
coef[i][j] = ((coef[i - 1][j] + (LL) coef[i - 1][j - 1] * 2 * j % MOD) % MOD + (LL) coef[i - 1][j - 2] * j % MOD * (j - 1) % MOD) % MOD;
}
}

inline void Solve ()
{
Init ();

F[N * 2 + 1][0] = 1;
int cnt0 = 0, cnt1 = 0;
for (int i = 2 * N; i >= 1; --i)
{
if (!is_key[i])
{
for (int j = 0; j <= cnt1; ++j)
F[i][j] = (LL) F[i + 1][j] * max (0, j - cnt0) % MOD;
++cnt0;
}
else
{
for (int j = 0; j <= cnt1 + 1; ++j)
{
ADD (F[i][j], F[i + 1][j]);
for (int k = 1; j + k <= cnt1 + 1; ++k)
{
ADD (F[i][j + k], (LL) F[i + 1][j] * C (cnt1 - j, k - 1) % MOD * coef[k - 1][k - 1] % MOD * (k + 1) % MOD);
}
}
++cnt1;
}
}

cout << (LL) F[1][N] * Pow ((MOD + 1) / 2, N) % MOD << endl;
}

inline void Input ()
{
N = read<int>();
for (int i = 1; i <= N; ++i) is_key[read<int>()] = 1;
}

int main ()
{

#ifdef hk_cnyali
freopen("ruins3.in", "r", stdin);
freopen("ruins3.out", "w", stdout);
#endif

MATH :: init ();
Input ();
Solve ();

return 0;
}