非常感谢洛谷的推荐题目功能。
我们知道,对两个集合内的元素取 \(\min\) 或 \(\max\) 是有很好的性质的,虽然我们都不会证。
举个例子,如果我们要求 \(\operatorname{and}\) 起来等于 \(1\sim n\) 的 \(k\) 元组个数,该怎么办?
我们可以先做一遍高维后缀和,此时设得到的数组 \(f_i\) 为是 \(n\) 的超集的数的个数。
我们发现其实我们在 \(n\) 的超集中选任意 \(k\) 个数,这 \(k\) 个数 \(\operatorname{and}\) 起来一定是 \(n\) 的超集。所以我们可以 \(f_i\gets \binom {f_{i}}{k}\)。此时 \(f_i\) 表示的则是 \(\operatorname{and}\) 起来是 \(n\) 的超集的 \(k\) 元组个数。我们发现 \(f_i\) 实质上可以拆解成 \(\operatorname{and}\) 起来是每个是 \(n\) 的超集的 \(k\) 元组个数之和(直接拆就行了,我当时第一次理解的时候理解了半天,太唐了),所以这个东西是一个高维后缀和,我们做一遍高维差分之后就是 \(\operatorname{and}\) 起来是 \(n\) 的 \(k\) 元组个数。
所以我们对集合取 \(\min\) 或 \(\max\) 在集合前后缀上体现的非常明显,基本在高维前/后缀和上转化一下权值再做一遍高维差分就能解决。\(k\) 元组问题是典型。
例题:P2714 四元组统计
注意到其实 \(\gcd\) 其实就是在约数指数这个集合内取 \(\min\),那么做一遍 Dirichlet 后缀和,然后把个数变成 \(4\) 元组的个数,然后再做一遍 Dirichlet 差分即可。
标签:min,后缀,max,个数,元组,operatorname,高维 From: https://www.cnblogs.com/xingyuxuan/p/18175739