【JOISC 2020 Day2】Ruins 3

题目

题目描述
题目译自 JOISC 2020 Day2 T3「最古の遺跡 3 / Ruins 3」

JOI 教授是 IOI 国有名的历史学家。他在研究 IOI 国一个古庙时发现了石柱的遗迹以及一篇古 IOI 国人写的文档。 在文档中，给出了这些石柱的相关描述，具体如下：

刚建好时，庙里有 根石柱，编号为 。对于任意 ，恰好有两根石柱的高度为 。
随后发生了 次地震，损坏了某些石柱，每次损坏将使石柱的高度减一。由于古人类的保护，其他石柱未被损坏，高度保持不变。
地震发生时，对于任意 ，古人类只能保护恰好一根高度为 的石柱。如果有多根石柱高度相同，根据古人类达成的共识，他们将选择保护编号最大的那一根。也就是说，如果石柱 在地震前高度是 ，古人类会去选择保护这根石柱当且仅当 且任意 满足 。
次地震后，只剩下 根石柱了，即只有 根石柱的高度至少为1。
JOI 教授觉得如果他能还原出来这些石柱地震前的高度，他能搞个大新闻。在他更仔细的研究后，发现 次地震后留下来的石柱的编号为 。他想知道原来的高度组合有多少种可能。因为你是 JOI 教授的学徒（pupil），他想让你写个程序计算这个方案数。

你的任务是编写一个程序，给出 次地震后留下来的石柱的编号，计算初始时 根石柱的高度组合种数模 。

输入格式
第一行一个整数 。

接下来一行 个空格分隔的整数 。

输出格式
输出题面描述中所求的方案数模 的值。

样例
样例输入 1
3
3 4 6
样例输出 1
5
样例解释 1
假设初始时石柱的高度为 。因为对于 的各个高度都恰好有 根石柱，因此符合题面描述中的条件。

第一次地震时，石柱 被古人类保护。地震后，石柱高度变为 。
第二次地震时，石柱 被古人类保护。地震后，石柱高度变为 。
第三次地震时，石柱 被古人类保护。地震后，石柱高度变为 。 三次地震后，石柱 留下来了，与输入一致。
除了这个例子，可能的高度组合还有 。

因此，总共有 种高度组合符合输入数据和题面描述的条件。

样例输入 2
1
1
样例输出 2
0
样例解释 2
本输入的唯一可能高度组合为 。地震后，石柱高度变为 。

因此，没有符合输入数据和题面描述给出的条件的初始高度组合。

样例输入 3
10
5 8 9 13 15 16 17 18 19 20
样例输出 3
147003663
样例解释 3
总共有 种符合条件的初始高度组合，将这个数除 余数为 ，即输出值。

数据范围与提示
对于 的数据，有 。

各子任务详情如下：

子任务编号 分值 特殊限制
1 6
2 52
3 42 无特殊限制
显示分类标签
1

或者，上传代码文件

思路

首先考虑hi确定如何选择剩下的柱子集和A
每次选出hi最大的两个下标，放进集合S，选取S中最大元素，放入A，重复n次
也有这样一个等价的过程：从后往前考虑各个 hi ，若在最终状态中，仍然存在 1≤x≤hi ，使得没有高度为 x 的石柱，则选取其中最大的 x ， i 处的石柱在最终状态中高度为 x 。

考虑DP
设dpi,j表示考虑了石柱 i,i+1,…,2N 在最终状态中已经存在高度 1,2,…,j

转移分两种：i∈A或i∉A
分类讨论一下即可

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1207,mod = 1e9 + 7;
int n,f[N],g[N],dp[N][N],b[N][N];
bool bz[N];
int main() 
{
	scanf("%d",&n);
	int c;
	for(int i = 1; i <= n; i++) scanf("%d",&c),bz[c] = 1;
	for(int i = 0; i <= n; i++) 
	{
		b[i][0] = 1;
		for(int j = 1; j <= n; j++) b[i][j] = (b[i - 1][j] + b[i - 1][j - 1]) % mod;
	}
	g[0] = 1;
	for(int t = 0; t < n; t++)
		for(int j = 0; j <= t; j++) {
			int i = t - j;
			g[i + j + 1] = (g[i + j + 1] + 1ll * g[i] * g[j] % mod * b[t][i] % mod * (j + 2)) % mod;
		}
	dp[2 * n + 1][0] = 1;
	int opt = 0,cnt = 0;
	for(int i = 2 * n; i >= 1; i--) 
	{
		if(!bz[i]) 
		{
			for(int j = 0; j <= cnt; j++) dp[i][j] = 1ll * dp[i + 1][j] * (j - opt) % mod;
			opt++;
		} 
		else 
		{
			for(int t = 0; t <= cnt; t++)
				for(int k = 0; k <= t; k++) 
				{
					int j = t - k;
					dp[i][j + k + 1] = (dp[i][j + k + 1] + 1ll * dp[i + 1][j] * (k + 2) % mod * g[k] % mod * b[cnt - j][k]) % mod;
				}
			for(int j = 0; j <= cnt; j++) dp[i][j] = (dp[i + 1][j] + dp[i][j]) % mod;
			cnt++;
		}
	}
	ll inv = (mod + 1) / 2;
	for(int i = 1; i <= n; i++) dp[1][n] = dp[1][n] * inv % mod;
	cout << dp[1][n] << endl;
}