最近对计数题的训练还是让我很有收获的。能想出这题的主状态，说明我有了一定的计数水平。但最后因为懒于编转移看了题解，其实这并没有必要。以后还是要自己把转移讨论出来，哪怕漏了几类也没有关系。毕竟考场上，状态和转移都需要自己推。
首先，有一个基本的观察：
每一次地震，对于最大的有两个位置的高度，靠右的那个位置一定会被保留下来，再也不会变化。
“最大的”，”靠右“，诸如此类的字眼，提示我们从后往前考虑问题，并从值域入手设计状态。
但现在还没有直接的思路，需要进一步观察。
从后往前推，对于第
个位置，它显然可以活着。
对于第 个位置，如果它和第
个位置都是 ，它就会寄，否则一定能活下来。
对于第 个位置，如果它是
，且后面有 ，或者它是 ，且后面也有 ，它就得寄，否则会活。
（注意，上述的状态都是在某次地震后的状态，不一定是最初的）
以此类推，我们发现：
如果在某次地震后，高度为
的柱子后面，高度为
的柱子都至少出现了一次，那这根柱子一定活不下来。
进一步地说，我们从后往前扫到一个位置 ，如果 没有在后面的位置出现过，那么 就是当前位置的最终值，否则 会一直减到后面没有出现 ，减到 为止。
事实上，这个“在后面没有出现”，你只需要考虑在后面的最终值中，
有没有出现，而不需要考虑“某次地震以后”，因为地震并不会缩小高度的集合，以前出现的高度，地震过后还是出现，这是显然的，而我们显然不会做多余的事情，因为基于最终值推导出的变化肯定需要执行。
那么我们就只需要考察 这些柱子高度的最终值 以及
形成这些最终值的方式
（这看上去是句废话，但你会发现，通过上面的观察，考察后者变得简单了很多）。
考察这些的柱子的最终值，它们会在值域上形成一些连续段，而与一个柱子的存亡有关的就是那个最低的连续段。
那么我们就可以设出状态
表示考虑到了位置 ，在最终值上， 的柱子都出现过，但 未出现过的答案。
有些读者可能会发现这个
长得很像 MEX，事实上，这题的转移与 CF1608F MEX Counting
的思想是相同的。我们接下来细说。
在下文，我们假设值相同的两个柱子是有区别的，最后将答案除以 。
为方便描述，接下来设 表示
中钦定倒塌的柱子数量， 表示
中钦定存留的柱子数量。
如果 位置钦定倒塌：
那么该位置的取值只能是 ，一共有
个数可以选择，而我们之前选
的时候已经用掉了 个数，还有 个数用在了那 个倒掉的柱子上，故这一位的方案数是
，故有转移式 。
如果 位置钦定存活：
那么需要分类讨论：
位置的最终值大于 ，此时我们不能确定什么，所以使用
CF1608F 中的”延迟贡献“思想，将这一个数留到后面再来确定，即转移 。
位置的最终值等于 ，那么我们所需要做的工作会复杂一些，我们可能要把值域上最小和次小的连续段拼起来。
考虑从 转移到 。
那么我们首先要确定
位置初始值该填什么，显然，其只能从 里面选（因为这些数都出现过 次了，在这里只有 的贡献），同时还可以选两个 ，总计 种选法。
然后考虑确定
的位置，我们当然只能在活着的柱子里选，目前只有
个活着的柱子等待决策的，故方案数为 。（这里就把情况
中的“延迟决策”放到了这一步进行计算）
对于这
个数，我们还要确定其初始值的填法，我们考虑计数这个东西需要解决什么限制。
我们需要在 这 个数中选出 个数，使得其在地震完之后是一个长度为
的排列。
这个条件还是很复杂，考虑必要条件：对于每个 ，值 的元素的个数 。
必要性显然，因为如果存在一个
使得不超过 的元素个数 ，那必然有一个柱子可以滑到 。
然后我们发现这个条件是充分的，因为这样的序列肯定不劣于一个排列（排列会把每个限制都取到等号），而排列一定合法。
基于上述条件，可以设计一个 表示填了数 ，一共用了 个位置的方案数。枚举当前数填 个转移即可：
汇总上述分析，得出转移式：
跑上述的 DP 即可。时间复杂度 。
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 6e2 + 5,P = 1e9 + 7;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
bool alive[N << 1];
int f[N << 1][N],g[N][N];
int n;
int C[N][N];
inline int Binom(int n,int m) { if(n < 0 || m < 0 || n < m) return 0;return C[n][m];}
int main()
{
cin >> n;
for(int i = 1,x;i <= n;i++)
cin >> x,alive[x] = true;
C[0][0] = 1;
for(int i = 1;i <= n;i++)
{
C[i][0] = C[i][i] = 1;
for(int j = 1;j < i;j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
}
g[0][0] = 1;
for(int i = 1;i <= n;i++)
{
g[i][0] = 1;
for(int j = 1;j <= i;j++)
{
Plus(g[i][j],g[i - 1][j]);
if(j) Plus(g[i][j],2ll * j * g[i - 1][j - 1] % P);
if(j > 1) Plus(g[i][j],1ll * j * (j - 1) * g[i - 1][j - 2] % P);
}
}
int sum = 0;
f[n * 2 + 1][0] = 1;
for(int i = n * 2;i >= 1;i--)
{
if(alive[i])
{
for(int j = 0;j <= n;j++)
{
Plus(f[i][j],f[i + 1][j]);
for(int k = 1;k <= j;k++)
Plus(f[i][j],1ll * f[i + 1][j - k] * Binom(sum - (j - k),k - 1) % P * (k + 1) % P * g[k - 1][k - 1] % P);
}
++sum;
}
else
{
int ded = n * 2 - i - sum;
for(int j = 0;j <= n;j++)
if(j >= ded)
Plus(f[i][j],1ll * f[i + 1][j] * (j - ded) % P);
}
}
int ans = 1ll * f[1][n] * qpow((P + 1) / 2,n) % P;
cout << ans << endl;
return 0;
}
|