星际探测

GitHub跳转原题关系图返回列表

按 D 排序把值域区间变成下标区间,用区间多项式 Π(1+V·y) 的系数表示初等对称和,容斥除掉最小 V 后乘 K!。

OJ: roj

题目 ID: 1755

难度:提高+/省选-

标签:线段树多项式组合计数前缀积python

创建: 2026-10-07 21:45

更新: 2026-10-07 21:45

形式化题目

给出 NN 块区域,第 ii 块用二元组 (Di,Vi)(D_i, V_i) 描述(所有 DiD_i 互不相同,所有 ViV_i 互不相同), 以及 QQ 个计划 (L,R,K)(L, R, K)。对一个计划记

S={ Vi∣L≤Di≤R },x=min⁡S.S = \{\, V_i \mid L \le D_i \le R \,\}, \qquad x = \min S .

在 S∖{x}S \setminus \{x\} 中有次序地挑 KK 块(顺序不同算不同方案),一个计划的评估值就是所有 方案元素乘积之和模 2322^{32}:

P=K!⋅eK(S∖{x}) mod 232,eK(T)=∑U⊆T∣U∣=K∏v∈Uv.P = K! \cdot e_K (S \setminus \{x\}) \bmod 2^{32}, \qquad e_K(T) = \sum_{\substack{U \subseteq T \\ |U| = K}} \prod_{v \in U} v .

每个 KK 元子集恰好对应 K!K! 个有序 KK 元组,所以「有次序」只贡献一个公共因子 K!K!, 剩下的 eKe_K 是 KK 次初等对称和。若 ∣S∣≤K|S| \le K,除了最小的一块已无可选区域,答案为 00。

用样例的第二个计划核对:D∈[2,6]D \in [2,6] 给出 S={4,2,3,1}S = \{4, 2, 3, 1\},x=1x = 1, 2!⋅e2({2,3,4})=2⋅(6+8+12)=522! \cdot e_2(\{2,3,4\}) = 2 \cdot (6 + 8 + 12) = 52,与输出一致。

正解

思路

第一步:按 DD 排序,把值域区间变成下标区间。 所有计划问的都是「DD 落在某个区间里的那些区域」, 而区域本身是静态的。把区域按 DD 升序排成一行后,一个有 kk 块区域的集合就恰好对应一个连续的下标段 [l,r][l, r]:二分求出第一个 D≥LD \ge L 的位置和最后一个 D≤RD \le R 的位置即可。于是问题变成 「在静态数组的一个下标段上求 eKe_K 并排除段内最小值」,与 DD 的具体数值无关了。

第二步:用一个多项式把区间内所有 eke_k 一次装下。 对下标段 [l,r][l, r] 定义

U[l,r](y)=∏i=lr(1+Vi y),U_{[l,r]}(y) = \prod_{i=l}^{r} \bigl(1 + V_i\, y\bigr),

它的 yKy^K 系数就是 eKe_K:展开时一个括号要么贡献 11、要么贡献 ViyV_i y,「选了哪些括号的 yy 项」正好 枚举出所有 KK 元子集,系数自然是这些子集的乘积之和。这一步是全部的枢纽——从「求一个组合数」 变成了「求一个多项式的系数」。

第三步:把最小的那一块除掉。 设 x=min⁡Sx = \min S,那么 U[l,r](y)U_{[l,r]}(y) 里属于 xx 的因子是 (1+xy)(1 + xy)。 把集合中的 xx 删掉,对应的操作就是把多项式除以 (1+xy)(1 + xy)。形式上(截断到 yKy^K 次)有

11+xy=1−xy+x2y2−x3y3+⋯ ,\frac{1}{1 + xy} = 1 - xy + x^2y^2 - x^3y^3 + \cdots,

因为把右边乘上 (1+xy)(1+xy) 后只剩 11 与高次项。只要 0∼K0 \sim K 次的系数,高于 KK 次的项丢弃不影响 低次系数,于是

eK(S∖{x})=[yK] U[l,r](y)⋅∑j≥0(−x)jyj=∑j=0K(−x) j eK−j(S),e0=1.e_K(S \setminus \{x\}) = [y^K]\, U_{[l,r]}(y) \cdot \sum_{j \ge 0} (-x)^j y^j = \sum_{j=0}^{K} (-x)^{\,j}\, e_{K-j}(S), \qquad e_0 = 1 .

这就是「容斥去掉最小块」的完整写法:只需要区间最小值和区间多项式的 0∼K0 \sim K 次系数。答案再乘 K!K! 即可。

实现一(C++):线段树维护多项式。 每个结点存该下标段的 e1∼e6e_1 \sim e_6、段内最小 VV 及它的位置。 两个结点合并时多项式相乘并截断,也就是

ei=eL[i]+eR[i]+∑j=1i−1eL[j]⋅eR[i−j].e_i = e_L[i] + e_R[i] + \sum_{j=1}^{i-1} e_L[j] \cdot e_R[i-j] .

单次询问二分定位下标段,查一次区间最小值,再沿线段树把 O(log⁡N)O(\log N) 个结点合并成区间多项式, 最后按上式容斥、乘 K!K!。所有系数用 unsigned int 存,溢出回绕恰好就是模 2322^{32}。

实现二(Python):前缀积 + 形式逆。 线段树一次询问要合并 Θ(log⁡N)\Theta(\log N) 个结点、每个结点 1515 次乘法,CPython 下 10510^5 次询问是上亿次运算,跑不动。改用一个更省常数的等价做法:

  • 记前缀积 Pm(y)=∏i<m(1+Viy)P_m(y) = \prod_{i<m} (1 + V_i y),那么 [l,r][l, r] 的多项式就是 U=Pr+1⋅Pl−1U = P_{r+1} \cdot P_l^{-1};
  • PlP_l 的常数项是 11,在截断幂级数环里永远可逆(形式逆),可以边扫边维护: 由 Pm=Pm+1 (1+vmy)P_m = P_{m+1}\,(1 + v_m y) 反解 Qm=Pm−1Q_m = P_m^{-1},得 qknew=qkold−vm qk−1newq_k^{new} = q_k^{old} - v_m\, q_{k-1}^{new}, 扫一个元素只要 O(K)O(K) 次乘法;
  • 区间最小值用稀疏表 O(1)O(1) 回答。

于是每次询问只剩 O(K2)O(K^2) 次乘法,总复杂度 O((N+Q)K2)O((N+Q)K^2)。注意「除以 PlP_l」不是整数除法: 这里的可逆性是多项式在形式幂级数意义下的(常数项为 11 即为可逆元),并且只截断到 KK 次, 高次项被丢掉不会影响低次系数,所以取模运算一路合法。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 21:45
# update_at: 2026-10-07 21:45

import sys
from bisect import bisect_left, bisect_right
from operator import mul

MOD = 1 << 32        # 评估值对 2^32 取模,也就是只留低 32 位
MASK = MOD - 1       # x & MASK 等价于 x mod 2^32
W = 7                # 每个多项式存 0..6 次共 7 个系数,K <= 6 够用

type Poly = tuple[list[int], list[int]]  # (前缀积多项式, 它的形式逆):每 7 个数一段的平铺表;
                                         # 逆的每一段是「次数从高到低」存放,询问时一次切片即得卷积序
type Rmq = list[list[int]]               # 稀疏表:第 k 行是长度 2^k 的区间最小值,用于查 [l, r] 最小 V

FAC = [1, 1, 2, 6, 24, 120, 720]         # K!,K <= 6


def build_prefix(vals: list[int]) -> Poly:
    """扫一遍 V,产出每个前缀的段积多项式 P[m] = Π_{i<m}(1 + V_i·y) 及其形式逆。

    P[m+1] = P[m]·(1 + v·y) 的每一项都只用到低一次的旧值,所以 p 从高次往低次原地递推:
    p_k ← p_k + v·p_{k-1};形式逆则从 P[m] = P[m+1]·(1 + v·y) 反解出
    q_k ← q_k - v·q_{k-1},其中的 q_{k-1} 必须是刚更新过的那一个,所以 q 反而从低次往高次递推。
    两边都是每扫一个 V 做 O(K) 次乘法。
    """
    pref = [1, 0, 0, 0, 0, 0, 0]  # P[0] = 1
    invp = [0, 0, 0, 0, 0, 0, 1]  # P[0] 的逆还是 1,逆序存放后正好是 7 个数一段
    p, q = [1, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0]
    for v in vals:
        for k in range(W - 1, 0, -1):  # 从高次往低次:p[k-1] 这一轮还没被新的覆盖
            p[k] = (p[k] + v * p[k - 1]) & MASK
        for k in range(1, W):          # 反解要的是新 q[k-1],所以从低次往高次
            q[k] = (q[k] - v * q[k - 1]) & MASK
        pref += p
        invp += q[::-1]
    return pref, invp


def build_rmq(vals: list[int]) -> Rmq:
    """区间最小值稀疏表:第 k 行的第 i 项是 [i, i+2^k) 的最小值。"""
    rmq = [vals]
    span = 1
    while span * 2 <= len(vals):
        prev = rmq[-1]
        rmq.append(list(map(min, prev, prev[span:])))  # 两段相邻的 2^k 段拼出长度 2^{k+1}
        span *= 2
    return rmq


def plan_value(poly: Poly, rmq: Rmq, l: int, r: int, k: int) -> int:
    """区域下标限定在 [l, r]、选取 k 块时,这一项计划的评估值(mod 2^32)。

    评估值 = k! × (去掉 V 最小那块后的 k 次初等对称和),而「去掉最小块」等于乘上
    (1 + min_v·y) 的形式逆 1 - min_v·y + min_v²·y² - …,所以只用一次区间最小值和
    [l, r] 多项式的前 k+1 个系数。
    """
    if r - l + 1 <= k:  # 还得先排除最小的一块,所以至少要 k+1 块区域;空区间也走这里
        return 0

    width = (r - l + 1).bit_length() - 1      # 两块长度 2^width 的区间盖住 [l, r]
    minv = min(rmq[width][l], rmq[width][r - (1 << width) + 1])

    pref, invp = poly
    tail = pref[(r + 1) * W:(r + 1) * W + W]  # [0, r+1) 的前缀积多项式
    head = invp[l * W:(l + 1) * W]            # [0, l) 前缀积的形式逆(Poly 约定的逆序块)
    # [l, r] 多项式 = 前缀积 · (左端前缀积)^{-1},第 j 个系数就是 j 次初等对称和;
    # head 是逆序块,所以第 j 个系数的点积要用 head 的尾段挨着 tail 的头段
    coef = [1] + [
        sum(map(mul, tail[:j + 1], head[W - 1 - j:])) & MASK for j in range(1, k + 1)
    ]

    acc, pw = 0, 1                            # pw 是 (-min_v)^j
    for j in range(k + 1):
        acc = (acc + pw * (1 if j == k else coef[k - j])) & MASK
        pw = pw * (MOD - minv) & MASK
    return acc * FAC[k] & MASK


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, q = next(data), next(data)

    ds = [next(data) for _ in range(n)]       # 每块区域的 D
    vs = [next(data) for _ in range(n)]       # 每块区域的 V
    order = sorted(range(n), key=ds.__getitem__)  # 按 D 升序,D 的区间就变成下标区间
    ds = [ds[i] for i in order]
    vs = [vs[i] for i in order]

    poly = build_prefix(vs)
    rmq = build_rmq(vs)

    out: list[str] = []
    for _ in range(q):
        L, R, k = next(data), next(data), next(data)
        l = bisect_left(ds, L)                # 第一个 D >= L 的位置
        r = bisect_right(ds, R) - 1           # 最后一个 D <= R 的位置
        out.append(str(plan_value(poly, rmq, l, r, k)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 21:45
 * update_at: 2026-10-07 21:45
 */

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned int u32; // 所有乘积之和都在 mod 2^32 下计算,u32 溢出回绕正好就是取模

const int MAXN = 100000 + 5; // 区域数上限
const int KMAX = 6;          // 单次勘测选取块数 K 的上限

// 一块区域:相对距离 D 与丰富程度 V
// V 用 u32:V <= 1e9,而所有参与计算的量都在 mod 2^32 意义下,统一用 u32 省掉转换
struct Area {
    ll d;
    u32 v;
};
Area a[MAXN]; // 读入后按 D 升序重排,这样 D 的区间查询就变成下标区间查询

// 线段树结点:维护该段 V 的 1..KMAX 次初等对称和,以及段内最小 V 及其位置
struct SegNode {
    u32 e[KMAX + 1]; // e[k] = 段内 V 的 k 次初等对称和(k >= 1;k = 0 恒为 1,不落数组)
    u32 min_v;       // 段内最小的 V
    int min_pos;     // 最小 V 的下标(按 D 排序后的位置,V 互不相同所以唯一)
};
SegNode tree[MAXN << 2];

int n, q; // 区域数、计划数

// 把 b 整段并进 a:a 表示某段的多项式,b 表示另一段,结果写回 a
// 两段的多项式相乘就是「V 集合取并」,系数按截断卷积合并:
//   e_i = a_i + b_i + Σ_{j=1}^{i-1} a_j · b_{i-j}
void merge_poly(u32 a[], const u32 b[]) {
    u32 c[KMAX + 1];
    for (int i = 1; i <= KMAX; i++) {
        u32 s = a[i] + b[i];
        for (int j = 1; j < i; j++) s += a[j] * b[i - j];
        c[i] = s;
    }
    for (int i = 1; i <= KMAX; i++) a[i] = c[i];
}

// 用两个儿子的信息重置结点 u:多项式做合并,最小 V 取较小的一边
void pull(int u) {
    int lc = u << 1, rc = lc | 1;
    if (tree[lc].min_v <= tree[rc].min_v) {
        tree[u].min_v = tree[lc].min_v;
        tree[u].min_pos = tree[lc].min_pos;
    } else {
        tree[u].min_v = tree[rc].min_v;
        tree[u].min_pos = tree[rc].min_pos;
    }
    for (int i = 1; i <= KMAX; i++) tree[u].e[i] = 0;
    merge_poly(tree[u].e, tree[lc].e); // 空多项式(全是 0)依次并上左右儿子
    merge_poly(tree[u].e, tree[rc].e);
}

// 建树:叶子就是一个 V,它的一次初等对称和就是 V 本身
void build(int u, int l, int r) {
    if (l == r) {
        for (int i = 1; i <= KMAX; i++) tree[u].e[i] = 0;
        tree[u].e[1] = a[l].v;
        tree[u].min_v = a[l].v;
        tree[u].min_pos = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pull(u);
}

u32 cur_min_v; // 询问区间内最小的 V
int cur_min_pos; // 它的下标

// 查 [ql, qr] 内最小的 V 及其位置:V 互不相同,所以位置唯一
void query_min(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        if (tree[u].min_v < cur_min_v) {
            cur_min_v = tree[u].min_v;
            cur_min_pos = tree[u].min_pos;
        }
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) query_min(u << 1, l, mid, ql, qr);
    if (mid < qr) query_min(u << 1 | 1, mid + 1, r, ql, qr);
}

// 把 [ql, qr] 的整段多项式并进 acc(acc 从「空集」的多项式开始累乘)
void query_poly(int u, int l, int r, int ql, int qr, u32 acc[]) {
    if (ql > r || qr < l) return;
    if (ql <= l && r <= qr) {
        merge_poly(acc, tree[u].e);
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) query_poly(u << 1, l, mid, ql, qr, acc);
    if (mid < qr) query_poly(u << 1 | 1, mid + 1, r, ql, qr, acc);
}

// 在按 D 升序的数组里找第一个 D >= x 的位置,都小于 x 时返回 n + 1
int first_ge(ll x) {
    int lo = 1, hi = n + 1;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (a[mid].d < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 在按 D 升序的数组里找最后一个 D <= x 的位置,都大于 x 时返回 0
int last_le(ll x) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo + hi + 1) >> 1;
        if (a[mid].d <= x) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

bool cmp_d(const Area &x, const Area &y) { return x.d < y.d; }

int main() {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i].d);
    for (int i = 1; i <= n; i++) scanf("%u", &a[i].v);

    sort(a + 1, a + n + 1, cmp_d);
    build(1, 1, n);

    // fac[k] = k!,因为「有次序地挑 K 块」把每种组合算了 K! 次
    u32 fac[KMAX + 1];
    fac[0] = 1;
    for (int i = 1; i <= KMAX; i++) fac[i] = fac[i - 1] * (u32)i;

    for (int t = 0; t < q; t++) {
        ll L, R;
        int K;
        scanf("%lld %lld %d", &L, &R, &K);

        int l = first_ge(L), r = last_le(R);
        // 可选区域不足 K 块(还要先排除掉 V 最小的那一块,所以至少要 K + 1 块)
        if (l > r || r - l + 1 <= K) {
            printf("0\n");
            continue;
        }

        cur_min_v = 0xFFFFFFFFu;
        cur_min_pos = -1;
        query_min(1, 1, n, l, r);
        u32 min_v = cur_min_v;

        // poly[i] = 区间内 V 的 i 次初等对称和(i = 0..K)
        u32 poly[KMAX + 1];
        for (int i = 0; i <= KMAX; i++) poly[i] = 0;
        query_poly(1, 1, n, l, r, poly);

        // 去掉 V 最小的那一块:整段多项式 U(y) = Π(1 + V_i·y),
        // 去掉因子 (1 + min_v·y) 等价于乘上它的形式逆 1 - min_v·y + min_v²·y² - ...
        // 于是「去掉最小块后」的 K 次对称和 A_K = Σ_{j=0}^{K} (-min_v)^j · E_{K-j}(E_0 = 1)
        u32 res = 0, pw = 1; // pw = (-min_v)^j
        for (int j = 0; j <= K; j++) {
            u32 ek = (j == K) ? 1 : poly[K - j];
            res += pw * ek;
            pw *= (0u - min_v);
        }

        printf("%u\n", res * fac[K]); // fac[K] 把组合还原成有次序的选取
    }
    return 0;
}

复杂度

main.cpp(线段树):建树 O(NK2)O(NK^2),单次询问 O(log⁡N⋅K2)O(\log N \cdot K^2), 总时间 O((N+Qlog⁡N) K2)O\bigl((N + Q\log N)\,K^2\bigr),空间 O(NK)O(NK)。随仓数据最大点(N=Q=105N = Q = 10^5、KK 取满 66) 实测约 0.100.10 s / 12.712.7 MB。

main.py(前缀积 + 形式逆):预处理 O(NK2+Nlog⁡N)O(NK^2 + N\log N),单次询问 O(K2+log⁡N)O(K^2 + \log N), 总时间 O((N+Q)K2+Nlog⁡N)O\bigl((N+Q)K^2 + N\log N\bigr),空间 O(NK+Nlog⁡N)O(NK + N\log N)。同一最大点实测约 0.650.65 s。 两者算法同阶(Python 版常数更小、还省掉了线段树的 log⁡\log),没有任何一侧退化成暴力。

总结

三件事叠起来就是本题:

  1. 模型:「有次序地挑 KK 块」把答案变成 K!⋅eKK! \cdot e_K,于是问题从枚举方案变成求初等对称和;
  2. 转换:按 DD 排序后,DD 的区间查询就是下标区间查询,值域与结构彻底解耦;
  3. 数据结构:区间多项式 U(y)=∏(1+Viy)U(y) = \prod (1+V_i y) 的系数就是全部 eke_k,合并结点即截断卷积; 去掉最小的那一块则靠 (1+xy)(1+xy) 的形式逆,展开成 ∑j(−x)jeK−j\sum_j (-x)^j e_{K-j} 的容斥式。

实现上有两条路。C++ 里线段树顺手把「区间最小 VV」和「区间多项式」一起维护, 单次询问 O(log⁡N⋅K2)O(\log N \cdot K^2),写起来最直白;Python 里为了压常数改用前缀积与其形式逆, 每次询问只剩 O(K2)O(K^2),代价是要自己想清楚「在截断幂级数里怎么除」,这也正是本题最值得回味的细节: 模 2322^{32} 下整数未必可逆,但常数项为 11 的多项式一定可逆。

素材说明:本题题面由公开题面重建(题面特征句对应五校联考 Melancholy),随仓 data/ 由素材源的 data.py 自造,可能与官方数据存在差异;素材源 std.cpp 与题面一致(样例及 1010 个数据点已用本解复算通过)。