题解 AT2366 【[AGC012F] Prefix Median】

· · 题解

题意

给定 n(1\le n\le 50) 与一个长度为 2n-1 的序列 a(1\le a_i\le 2n-1)，求有多少个排列 p 能够由此生成：

  1. 随机打乱排列 a
  2. 令 p_i=\{a_1,a_2..a_{2i-1}\} 中的中位数
\rm Sol:

不妨先考虑怎么样的一个序列 p 是能被生成的。

我们将原问题视为，初始有一个数 a_1，其单独构成集合 S，同时令 p_1=a_1

接下来每次选取 \{a\} 中未被加入的两个数一起加入 S，然后令 p_i 为集合 S 的中位数。

于是我们可以发现，如果每次加入的两个数比 p_{i-1} 大，那么中位数会变成其后继，如果都比 p_{i-1} 小则都变成其前驱，否则不变。

同时，我们如果对于序列 a 进行排序（方便起见不妨认为所有数都是不同的），那么对于其中的第 i 个数，其能成为中位数等价于比他大的数不能比 (2n-1)-i 多，比他小的数不能比 i-1 多，于是第 i 个数最多只能成 p_{1,2..\min(i,2n-i)} 上的数字。

反过来思考，我们发现 p_i 的值只能取排名为 [i,2n-i] 的 a_j 作为其值。

这个条件是一个必要条件，但不充分，我们发现一个 p 要合法其实他还需要满足在我们往集合添数的过程中中位数只能变成后继或者前驱的性质。

换而言之，假设考虑排列 \{p\} 中的第 i 与 i+1 个数，如果 p_i\ne p_{i+1}，则对于 p_{i+1}>p_i，有 \{p_1...p_{i-1}\} 中的所有 j 都应该满足 p_i< p_{i+1}<p_j，即 p_{i+1} 不是后继的情况非法，同理于前驱。

这个条件配上之前的那个条件后充分吗？充分。

手玩可以比较感性的得到？

对于满足上述条件的 p 数组，我们总能够构造一个合法的 a 使得他生成的 p 数组满足条件，不妨考虑如下构造：

对于每个不同的 p_i，取其第一次出现的位置为 关键位置，将没有出现过的数字设为集合 A，那么如果 p_i>p_{i-1} 且当前 p_i 为关键位置，根据转换后的问题，我们往集合内加入 p_i 与 A 中剩余的最大值，若 p_i<p_{i-1}，则加入 A 中最小值与 p_i，如果不是关键位置，那么加入 A 中最小值和最大值。

容易发现由于限制 1 即 a_i\le p_i\le a_{2n-i}，这样总可以构造出一个合法的 a 序列使得其生成序列为 p

于是我们的条件等价于：

  1. a_i\le p_i\le a_{2n-i}
  2. p_i\in \{a_1,a_2...a_{2n-1}\}
  3. 对于 i 和 i+1，不存在 j 满足 p_i<p_j<p_{i+1} 或 p_i>p_j>p_{i+1}

假设通过 dp 来进行计数，那么较为困难的就是限制 3 的处理，不过我们发现，如果我们从 n 到 1 进行填数，那么每次填入一个 p_{k} 之后，都应该有其作为 j 要合法，我们将之前的 p 集在值域上存在过的值分别标记，于是当前的 p 不能被任何一个 (p_i,p_{i+1}) 描述的区间包含。

我们发现问题可以转换为：

初始有一个数 a_n，且其构成一个集合 S，对于从后往前第 i 次操作，令 l， r 分别表示 n-l+1,n+r-1，且初始您拥有一个权值 x=a_n，那么每次操作等价于：

将 a_{l} 与 a_{r} 加入集合 S，然后去重并排序，然后您选择一个权值 y，然后将所有权值位于两者之间 (x,y) 的值删除（不包括端点），事实上，如果将 S 内部的元素进行排序，那么问题等价于在不断序列上删除区间，以及增加序列的最左/右端点，问题等价于拥有一个端点并且不断的移动他的过程。

注意到，如果 a_{l}=a_{l+1}，那么 a_{l+1} 一定不会被删除，本次加点也无效，同理于 a_r

由于移动有两种方向，实际上你会发现我们只关注在当前位置左边和右边两边分别的待选择的 a 的数量。

于是令 f_{i,j,k} 表示从后往前考虑到第 i 位，待选择的在当前位置左边的数有 j 个，右边的数有 k 个的方案数即可，将向两边跑分别转移一下即可，复杂度 O(n^4)

Code: 
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
    char cc = getchar() ; int cn = 0, flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
    return cn * flus ;
}
const int N = 100 + 5 ; 
const int P = 1e9 + 7 ; 
int n, a[N], dp[N][N][N] ; 
signed main()
{
    n = gi() ; int m = 2 * n ; 
    for( re int i = 1; i < m; ++ i ) a[i] = gi() ; 
    sort( a + 1, a + m ) ;
    dp[n][0][0] = 1 ; 
    for( re int i = n - 1; i >= 1; -- i ) {
        int dl = ( a[i] != a[i + 1] ), dr = ( a[m - i] != a[m - i - 1] ) ;
        rep( l, 0, m ) {
            rep( r, 0, m ) {
                dp[i][l + dl][r + dr] = ( dp[i][l + dl][r + dr] + dp[i + 1][l][r] ) % P ; 
                for( re int k = 0; k < l + dl; ++ k )
                    dp[i][k][r + 1 + dr] = ( dp[i][k][r + 1 + dr] + dp[i + 1][l][r] ) % P ; 
                for( re int k = 0; k < r + dr; ++ k )
                    dp[i][l + 1 + dl][k] = ( dp[i][l + dl + 1][k] + dp[i + 1][l][r] ) % P ; 
            }
        }
    }
    int Ans = 0 ; 
    rep( l, 0, m ) rep( r, 0, m ) Ans = ( Ans + dp[1][l][r] ) % P ;
    cout << Ans << endl ; 
    return 0 ;
}