CF367E 题解

歪逼 · 2021-11-09 16:20:34 · 题解

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

若 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 必须做左端点，只有两种情况。时间复杂度 O(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;
}

update: 数据范围已更正，感谢提醒