\(\mathcal{Description}\)

Link.

给定序列 \(\{a_{2n-1}\}\)，将 \(\{a_{2n-1}\}\) 按任意顺序排列后，令序列 \(b_i\) 为前 \(2i-1\) 个数的中位数。求 \(\{b_n\}\) 的个数，对 \(10^9+7\) 取模。

\(n\le50\)。

\(\mathcal{Solution}\)

\(\{b_n\}\) 有一个很 naive 的性质：\(b_n\) 是常数，是 \(\{a_{2n-1}\}\) 的中位数。

考虑扩展这一性质，从后往前，\(b_{i+1}\) 所对应的 \(a\) 序列删去两个数后就得到 \(b_i\) 所对应的序列。显然，\(b_i\) 要么是 \(b_{i+1}\) 在新序列的前驱或后记，要么不变。

形式地，有性质：

\[(\forall i\in[1,n))(\not\exists j\in[1,n])(b_i<b_j<b_{i+1}\lor b_{i+1}<b_j<b_i)
\]

接着，考虑到中位数本身的性质，将 \(\{a_{2n+1}\}\) 升序排列后，可以确定每个 \(b_i\) 的范围：

\[a_i\le b_i\le a_{2n-i}
\]

那么设状态 \(f(i,j,k)\) 表示确定前 \(i\) 位，中位数左边有 \(j\) 个数可用，右边有 \(k\) 个数可用的方案数。转移就……看代码吧 www~

\(\mathcal{Code}\)

#include <cstdio>

#include <algorithm>

const int MAXN = 50, MAXM = 100, MOD = 1e9 + 7;

int n, m, a[MAXM + 5], f[2][MAXM + 5][MAXM + 5];

inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }

int main () {

	scanf ( "%d", &n ), m = 2 * n;

	for ( int i = 1; i < m; ++ i ) scanf ( "%d", &a[i] );

	std::sort ( a + 1, a + m );

	f[0][0][0] = 1;

	for ( int i = n, t = 0; i > 1; -- i, t ^= 1 ) {

		bool dl = a[i] ^ a[i - 1], dr = a[m - i + 1] ^ a[m - i];

		for ( int j = 0; j < m; ++ j ) {

			for ( int k = 0; k < m; ++ k ) {

				int& cur = f[t][j][k];

				if ( ! cur ) continue;

				addeq ( f[t ^ 1][j + dl][k + dr], cur );

				for ( int p = 0; p < j + dl; ++ p ) addeq ( f[t ^ 1][p][k + dr + 1], cur );

				for ( int p = 0; p < k + dr; ++ p ) addeq ( f[t ^ 1][j + dl + 1][p], cur );

				cur = 0;

			}

		}

	}

	int ans = 0;

	for ( int i = 0; i < m; ++ i ) {

		for ( int j = 0; j < m; ++ j ) {

			addeq ( ans, f[n & 1 ^ 1][i][j] );

		}

	}

	printf ( "%d\n", ans );

	return 0;

}

巴特西

Solution -「AGC 012F」「AT 2366」Prefix Median

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章