按 D 排序把值域区间变成下标区间,用区间多项式 Π(1+V·y) 的系数表示初等对称和,容斥除掉最小 V 后乘 K!。
OJ: roj
题目 ID: 1755
难度:提高+/省选-
标签:线段树多项式组合计数前缀积python
创建: 2026-10-07 21:45
更新: 2026-10-07 21:45
形式化题目
给出
在
每个
用样例的第二个计划核对:
正解
思路
第一步:按
第二步:用一个多项式把区间内所有
它的
第三步:把最小的那一块除掉。 设
因为把右边乘上
这就是「容斥去掉最小块」的完整写法:只需要区间最小值和区间多项式的
实现一(C++):线段树维护多项式。 每个结点存该下标段的
单次询问二分定位下标段,查一次区间最小值,再沿线段树把 unsigned int 存,溢出回绕恰好就是模
实现二(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()/**
* 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(线段树):建树
main.py(前缀积 + 形式逆):预处理
总结
三件事叠起来就是本题:
- 模型:「有次序地挑
块」把答案变成 ,于是问题从枚举方案变成求初等对称和; - 转换:按
排序后, 的区间查询就是下标区间查询,值域与结构彻底解耦; - 数据结构:区间多项式
的系数就是全部 ,合并结点即截断卷积; 去掉最小的那一块则靠 的形式逆,展开成 的容斥式。
实现上有两条路。C++ 里线段树顺手把「区间最小
素材说明:本题题面由公开题面重建(题面特征句对应五校联考 Melancholy),随仓 data/ 由素材源的
data.py 自造,可能与官方数据存在差异;素材源 std.cpp 与题面一致(样例及