题解：P7213 [JOISC2020] 最古の遺跡 3

厉害数数题，使我螺旋升天。然后是小蒟蒻看完题解后的感想，不得不说第一眼看是真的一头雾水。

先考虑给定初始高度如何求最终高度。题目说每次地震会使得相同高度的两个柱子（显然至多两个）中靠前的那个高度减一，不可能模拟整个过程，所以需要观察一些性质：

记一段后缀的高度集合为

A

，那么经过若干轮地震后高度集合

B

必然满足

A\in B

，即地震后高度集合元素不减。这不难归纳证明。

这启示我们从后往前逐个确定最终高度，已确定

[i+1,2n]

，现考虑

i

。由性质知只需关注

[i+1,2n]

中柱子的最终高度。具体而言，记

h_i

为当前柱子的初始高度，

H

为

[i+1,2n]

中柱子的高度集合，那么若

H

中存在极大连续段

[k,h_i]

则当前柱子高度最终变成

k-1

。

考虑 dp，记

f_{i,j}

为后

i

个柱子高度集合中存在极大连续段

[1,j]

的方案数。为了方便计数，认为同一高度的柱子不一样（两种颜色），最终除

2^n

即可。

考虑转移，记

c_0,c_1

为此前消失、保留的柱子数量：

当前柱子应消失：对 $j$ 无影响，只需考虑当前柱子的起始高度。由结论可知添加柱子的过程中连续段一定扩大，所以此前消失的柱子高度必然 $\le j$ 。那么有 $2j-j-c_0=j-c_0$ 种选择。即 $f_{i-1,j}\times (j-c_0)\to f_{i,j}$ 。
当前柱子应保留：需要根据对连续段 $[1,j]$ 的影响分类：
1. 最终高度 $>j+1$ ：无影响，但是可能影响其它连续段，怎么办？可以暂时存着，记为“待定柱”，等到连续段合并时再考虑其取值。即 $f_{i-1,j}\to f_{i,j}$ 。
2. 最终高度 $=j+1$ ：会合并连续段，枚举 $[1,j]$ 通过 $j+1$ 与 $[j+1,k]$ 合并。共有 $c_1-j$ 个待定柱，抽出一些构成连续段 $[j+1,k]$ ，不妨记 $g_k$ 为 $k$ 个柱子最终构成大小为 $k$ 的连续段的方案数。转移： $f_{i-1,j}\times {{c_1-j}\choose {k-j-1}}\times g_{k-j-1}\times (k-j+1)\to f_{i,k}$ 。

最后考虑

g_k

怎么求，不妨设构成的连续段为

[1,k]

。同

f

的转移，枚举最后添加的柱子高度

i

，那么此前连续段

[1,i-1]

和

[i+1,k]

的形成完全独立，这不难理解。

于是有转移：

g_k=\sum\limits_{i=1}^k {{k-1}\choose {i-1}}\times g_{i-1}\times g_{k-i}\times (k-i+2)

。

复杂度

O(n^3)

，跑的挺快。

代码

CPP

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define ADD(a, b) a = (a + b) % mod
const int N = 1.2e3 + 5, mod = 1e9 + 7, inv2 = 5e8 + 4;
int n, a, g[N], f[N][N], jc[N], jcinv[N];
bool vis[N];

inline int qstp(int a, int k) {int res = 1; for(; k; a = a * a % mod, k >>= 1) if(k & 1) res = res * a % mod; return res;}
inline int C(int n, int m){
	if(n < 0 || m < 0 || n < m) return 0;
	return jc[n] * jcinv[m] % mod * jcinv[n - m] % mod;
}
signed main(){
	jc[0] = jcinv[0] = 1;
	for(int i = 1; i < N; ++i) jcinv[i] = qstp(jc[i] = jc[i - 1] * i % mod, mod - 2);
	
	cin >> n;
	for(int i = 1; i <= n; ++i) scanf("%lld", &a), vis[a] = true;
	
	g[0] = f[0][0] = 1;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= i; ++j)
			ADD(g[i], g[j - 1] * g[i - j] % mod * (i - j + 2) % mod * C(i - 1, j - 1) % mod);
			
	int c0, c1 = 0;
	for(int i = 1; i <= 2 * n; ++i){
		c0 = i - 1 - c1;
		if(!vis[2 * n - i + 1]){
			for(int j = 0; j <= n; ++j) 
				if(j > c0) ADD(f[i][j], f[i - 1][j] * (j - c0) % mod);
		}
		else{
			for(int j = 0; j <= n; ++j){
				if(n > j + 1) ADD(f[i][j], f[i - 1][j]); 
				for(int k = j + 1; k <= n; ++k)
					ADD(f[i][k], f[i - 1][j] * g[k - j - 1] % mod * C(c1 - j, k - j - 1) % mod * (k - j + 1) % mod);
			}
		}
		c1 += vis[2 * n - i + 1];
	}
	
	cout << f[2 * n][n] * qstp(inv2, n) % mod;
	return 0;
}

题解：P7213 [JOISC2020] 最古の遺跡 3

文章操作

代码

相关推荐

评论

题解：P7213 [JOISC2020] 最古の遺跡 3