1 条题解
-
2
CF367E题解
有 个区间，你需要为每个区间分配左右端点 ， ()，使得区间两两互不包含且至少存在一个区间 的左端点等于 ，输出方案数对 取模的结果。
, 。
若 肯定无解，因为一定存在两个左端点相同的区间，而这两个区间定是包含关系。这样可以得到 。
考虑确定了 个左端点和 个右端点，区间无标号，有几种组合方案。假设 到 有序， 到 也有序， 区间两两不包含，即 ， 且 。如果 和 组成一个区间， 和 组成区间，显然有 ，，这样就有包含关系了，所以 只能和 组合。同理，得到 只能和 组合，所以方案是唯一的。
这样问题转换为选出 个左端点和 个右端点的方案，区间有标号最后需要在乘以 。设 表示前 个数，选了 个左端点和 个右端点。注意右端点个数不能大于左端点个数 ( )，否则是不合法的。
转移很简单，四种情况： 不选、 做左端点、 做右端点、 既做左端点又做右端点。当 是 必须做左端点，只有两种情况。时间复杂度 ，空间会炸所以要用滚动数组或压掉一维。
CODE
#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; }
- 1
