CF367E 题解

有 $n$ 个区间，你需要为每个区间分配左右端点
$l$，$r$ ($1 \le l \le r \le m$)，使得区间两两互不包含且至少存在一个区间
的左端点等于 $x$，输出方案数对 $10^9 + 7$ 取模的结果。

$1 \le n,m \le 10^5$, $1 \le x \le m$。

若 $n >m$ 肯定无解，因为一定存在两个左端点相同的区间，而这两个区间定是包含关系。这样可以得到 $n \le \sqrt{10^5}$。

考虑确定了 $n$ 个左端点和 $n$ 个右端点，区间无标号，有几种组合方案。假设 $l_1$ 到 $l_n$ 有序，$r_1$ 到 $r_n$ 也有序，
区间两两不包含，即 $\forall i,j \in [1,n]$，$l_i < l_j$ 且 $r_i < r_j$。如果 $l_1$ 和 $r_x(x>1)$ 组成一个区间，$r_1$ 和 $l_y$ 组成区间，显然有 $l_1 < l_y$，$r_1 < r_x$，这样就有包含关系了，所以 $l_1$ 只能和 $r_1$ 组合。同理，得到 $l_i$ 只能和 $r_i$ 组合，所以方案是唯一的。

这样问题转换为选出 $n$ 个左端点和 $n$ 个右端点的方案，区间有标号最后需要在乘以 $n!$。设 $f_{i,j,k}$ 表示前 $i$ 个数，选了 $j$ 个左端点和 $k$ 个右端点。注意右端点个数不能大于左端点个数 ( $k \le j$ )，否则是不合法的。

转移很简单，四种情况：$i$ 不选、$i$ 做左端点、$i$ 做右端点、$i$ 既做左端点又做右端点。当 $i=x$ 是 $i$ 必须做左端点，只有两种情况。时间复杂度 $\Theta(n^2m)$，空间会炸所以要用滚动数组或压掉一维。

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

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}

#define N 320
#define P 1000000007
#define int long long

int n, m, x, f[N][N];

signed main() {
	n = read(), m = read(), x = read();
	if (n > m) return puts("0"), 0;

	memset(f, 0, sizeof f), f[0][0] = 1;

	for (int i = 1; i <= m; i ++) {
		for (int j = n; j >= 0; j --) {
			for (int k = j; k >= 0; k --) {
				if (i == x) f[j][k] = 0;
				if (j > 0) (f[j][k] += f[j - 1][k]) %= P;
				if (i != x && k > 0) (f[j][k] += f[j][k - 1]) %= P;
				if (j > 0 && k > 0) (f[j][k] += f[j - 1][k - 1]) %= P;
			}
		}
	}

	int res = f[n][n];
	for (int i = 1; i <= n; i ++) {
		(res *= i) %= P;
	}
	printf("%lld\n", res);
	return 0;
}