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

_Cheems · 2024-11-20 15:56:58 · 题解

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

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

记一段后缀的高度集合为 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)，跑的挺快。

代码

#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;
}