自动搬运

查看原文

来自洛谷，原作者为

	crashed 让我们登上这座山！

搬运于2025-08-24 22:27:44，当前版本为作者最后更新于2021-02-18 20:02:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目

点这里看题目。

分析

懂了懂了，数数题都是毒瘤。

考虑我们可以怎么去震柱子。显然我们可以从高往低去震，但是这样分析无法导出一个解法。

另一个方式就是从后往前去震；这样我们可以导出一个结论：

如果当前柱子之后有高度为 $1\sim h$ 的柱子各一根，那么当前柱子及之前的柱子，如果高度 $\le h$，都会被直接震没。

因此我们可以将最大的 $h$ 看作 " 高度阈值 " ，把那 $1\sim h$ 的 $h$ 个柱子称为 " 标准柱 " 。

---

考虑一个 DP ：

$f_{i,j}$ 表示后 $i$ 个柱子，此时高度阈值为 $j$ 时的方案数。

为了便于转移，设两个参数 $c_0$ 为后 $i-1$ 个柱子中钦定消失的数量，$c_1$ 为钦定存在的数量。

此外，我们需要区分一下同样高度的两个柱子（比如染色）以便转移，最终答案就需要除掉 $2^n$。

分类讨论一下转移：

• 如果 $i$ 钦定消失，那么阈值不变，从 $f_{i-1,j}$ 转移。

  此时有 $2j$ 个可用高度，其中有 $j$ 个分配给了标准柱，还有 $c_0$ 个已经分配，所以系数为 $j-c_0$。

• 如果 $i$ 钦定保留，我们同样考虑它的高度：

  • 如果 $i$ 的高度 $> j+1$，我们就稍后考虑它的真实高度，此时从 $f_{i-1,j}$ 转移，系数为 1。

  • 如果 $i$ 的高度为 $j+1$，由于有些标准柱的高度还未确定，所以我们需要考虑接起来之后的高度阈值。

    枚举一个新阈值 $k$，此时是从 $f_{i-1,j}$ 转移到 $f_{i,k}$。

    计算系数，有如下几个部分：

    • 选定标准柱的位置 $\binom{c_1-j}{k-j-1}$。
    • 确定当前柱子的长度 $k-j+1$，分析方式同第一种转移。
    • 考虑未确定的 $k-j-1$ 的形成过程，这里我们用 $g_{k-j-1}$ 表示。

    因此系数为 $\binom{c_1-j}{k-j-1}\times g_{k-j-1}\times (k-j+1)$。

现在我们考虑 $g$ 的转移，明确 $g$ 的含义为 " 将 $n$ 个石柱震为高度连续的（初始）状态数 " 。

其实这个过程很类似于 $f$ 的第二种转移。我们只需要枚举一下编号最小的柱子的高度：

$$g_n=\sum_{i=1}^{n}\binom{n-1}{i-1}\times (i+1)\times g_{i-1}\times g_{n-i} $$

这样做的时间复杂度即 $O(n^3)$。

代码

#include <cstdio>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

typedef long long LL;

const int mod = 1e9 + 7, inv2 = ( mod + 1 ) >> 1;
const int MAXN = 2e3 + 5;

template<typename _T>
void read( _T &x )
{
	x = 0;char s = getchar();int f = 1;
	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
	x *= f;
}

template<typename _T>
void write( _T x )
{
	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
	if( 9 < x ){ write( x / 10 ); }
	putchar( x % 10 + '0' );
}

template<typename _T>
_T MAX( const _T a, const _T b )
{
	return a > b ? a : b;
}

int f[MAXN][MAXN];
int g[MAXN];

int C[MAXN][MAXN];
int N, M;
bool save[MAXN];

inline int Mul( LL x, int v ) { return x * v % mod; }
inline int Sub( int x, int v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, int v ) { return ( x += v ) >= mod ? x - mod : x; }

void Init()
{
	rep( i, 0, M )
	{
		C[i][0] = C[i][i] = 1;
		rep( j, 1, i - 1 )
			C[i][j] = Add( C[i - 1][j], C[i - 1][j - 1] );
	}
}

int main()
{
	read( N );
	rep( i, 1, N ) { int a;
		read( a ), save[a] = true;
	}
	M = N << 1, Init();
	
	g[0] = 1;
	rep( i, 1, M ) rep( j, 1, M )
		g[i] = Add( g[i], Mul( C[i - 1][j - 1], Mul( j + 1, Mul( g[j - 1], g[i - j] ) ) ) );
	f[M + 1][0] = 1; int c0 = 0, c1 = 0;
	per( i, M, 1 ) 
		if( save[i] )
		{
			c1 ++;
			rep( j, c0, c1 - 1 )
			{
				f[i][j] = Add( f[i][j], f[i + 1][j] );
				rep( k, 1, c1 - j )
					f[i][j + k] = Add( f[i][j + k], Mul( f[i + 1][j], Mul( C[c1 - j - 1][k - 1], Mul( g[k - 1], k + 1 ) ) ) );
			}
		}
		else
		{
			c0 ++;
			rep( j, c0, c1 )
				f[i][j] = Add( f[i][j], Mul( f[i + 1][j], j - c0 + 1 ) );
		}
	rep( i, 1, N ) f[1][N] = Mul( f[1][N], inv2 );
	write( f[1][N] ), putchar( '\n' );
	return 0;
}