526互联

[JOISC2020] 最古の遺跡 3

发布时间 2023-12-20 11:15:11作者: 灰鲭鲨

[JOISC2020] 最古の遺跡 3

题目背景

JOI 教授是一名研究 IOI 王国的历史学家。

题目描述

他发现了一行古代石柱的废墟及一份古代文献。

古代文献上的记载如下：

  • 刚建造完成的时候，有 \(2\times N\) 个石柱，对于 \(1\le k\le N\) 均有两个石柱高度为 \(k\)，同时记第 \(i\) 个石柱的高度为 \(h_i\)。
  • 会发生 \(N\) 次地震，每次地震会使一些石柱的高度 \(-1\)，其他石柱高度不变。
  • 石柱 \(i\) 地震时高度不变，当且仅当 \(h_i\ge 1\) 并且对于 \(j>i\) 都要有 \(h_i\not=h_j\)
  • \(N\) 次地震后，恰好只剩下了 \(N\) 个石柱。

现在 JOI 教授找出了仅存的 \(N\) 个石柱的位置 \(A_1,A_2,\ldots,A_N\)，他想让你求出，最初 \(2\times N\) 个石柱高度的修建方案数 \(\bmod~10^9+7\) 的值。

输入格式

第一行为一个整数 \(N\)。

接下来一行 \(N\) 个数，表示 \(A_1,A_2,\ldots,A_N\)。

输出格式

仅一行一个整数，表示最初 \(2\times N\) 个石柱高度的建造方案数 \(\bmod~10^9+7\) 的值。

样例 #1

样例输入 #1

3
3 4 6

样例输出 #1

5

样例 #2

样例输入 #2

1
1

样例输出 #2

0

样例 #3

样例输入 #3

10
5 8 9 13 15 16 17 18 19 20

样例输出 #3

147003663

提示

样例解释

样例 1 解释

一种可行的解为 \((2,2,3,3,1,1)\)。

  • 第一次地震后，变为 \((1,2,2,3,0,1)\)。
  • 第二次地震后，变为 \((0,1,2,3,0,1)\)。
  • 第三次地震后，变为 \((0,0,2,3,0,1)\)。

另外四种解如下：

  • \((2,3,2,3,1,1)\)。
  • \((2,3,3,2,1,1)\)。
  • \((3,2,2,3,1,1)\).
  • \((3,2,3,2,1,1)\)。

样例 2 解释

对于 \(N=1\) 的情况，显然只有 \((1,1)\) 一种修建方案，在一次地震后，会变为 \((0,1)\)，\(1\) 号位置不可能有石柱。

样例 3 解释

共有 \(111147004440\) 种可能的修建方案，\(111147004440 \bmod 10^9+7=147003663\)。

子任务

对于 \(100\%\) 的数据，保证 \(1\le N\le 600\)，\(1\le A_i\le 2\times N\)，\(A_i< A_{i+1}\)。

Subtask 编号 \(N\le\) 分数
\(1\) \(13\) \(6\)
\(2\) \(60\) \(52\)
\(3\) 无 \(42\)

先强制钦定两个相同高度的是不一样的，最后再除回去。 ``
先想在给出 \(h\) 的情况下，如何不模拟找到 \(A\)。

看题解可知倒序枚举 \(h\)。用一个 \(vs\) 数组表示在最终态时有哪些数出现过（容易发现每种数最多出现一次）。如果 \(vs_{h_i}\)，那么\(h_i\) 至少被减了一次，\(--h_i\)，直到 \(h_i=0\) 或者他没有出现过。如果没有出现过，那么他不可能被删除，这个位置就属于 \(A\)。

那么现在给出了 \(A\)，我们要倒退回原来的 \(h\) 的方案数。容易状压 \(n2^n\)。考虑给某一个 不在 \(A\) 的数填的时候有多少种方案。考虑维护 \(vs\) 数组的信息，他不在 \(A\) 中说明他在 \(vs\) 数组的前缀1中。那么就记录前缀1的数量。定义 \(f _{i,j}\) 表示考虑到倒数第 \(i\) 个数，\(vs\) 数组前缀有 \(j\) 个1的方案数。那么如果后面有 \(c\) 个数是不属于 \(A\) 的，就有 \(j-c\) 种方案。

现在看如果倒数第 \(i\) 个数是在 \(A\) 中的，那现在有两种情况。一种是前缀1的个数没有改变，那么这里的系数之后再考虑。如果前缀1的个数发生了改变，说明他填到了 \(j+1\) 处，枚举此时的前缀1的个数是 \(k\)。如果后面总共有 \(s\) 个属于 \(A\) 的点，那么方案乘上 \(\binom{s-j}{k-j-1}\times dp_{k-j-1}\times (k-j+1)\)，\(dp_i\) 表示有 \(i\) 个连续的数的填的方案数，\(k-j+1\) 表示这个柱子的高度。

考虑求出 dp 值。\(dp_i=\sum\limits_{j=1}^idp_{j-1}\times dp_{i-j}\times\binom{i-1}{j-1}\times (j+1)\)，分析同上。

#include<bits/stdc++.h>
using namespace std;
const int N=1205,P=1e9+7;
int dp[N],f[N],g[N],n,m,a[N],C[N][N],v[N];
int main()
{
	scanf("%d",&n),m=n<<1;
	for(int i=C[0][0]=1;i<N;i++)
	{
		C[i][0]=C[i][i]=1;
		for(int j=1;j<N;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
	}
	for(int i=1;i<=n;i++)
		scanf("%d",a+i),v[m-a[i]+1]=1;
	dp[0]=1; 
	for(int i=1;i<=m;i++)
		for(int j=1;j<=i;j++)
			(dp[i]+=1LL*dp[j-1]*dp[i-j]%P*C[i-1][j-1]%P*(j+1)%P)%=P;
	f[0]=1;
	int c=0,s=0;
	for(int i=1;i<=m;i++)
	{
		if(!v[i])
		{
			for(int j=c;j<=n;j++)
				f[j]=1LL*f[j]*(j-c)%P;
			++c;
		}
		else
		{
			++s;
			for(int j=s;j>=c;j--)
				for(int k=j+1;k<=s;k++)
					(f[k]+=1LL*C[s-j-1][k-j-1]*dp[k-j-1]%P*(k-j+1)%P*f[j]%P)%=P;
		}
	}
	for(int i=1;i<=n;i++)
		f[n]=f[n]&1? f[n]+P>>1:f[n]>>1;
	printf("%d\n",f[n]);
}