2025-06-24 随笔

离线 O(1) 求逆元

一个很平凡的技巧，但是确实可以降低代码的常数或者复杂度。

假如我们有一个长度为 $n$ 的序列 $x_1,\cdots,x_n$，我们需要求 $x_1^{-1},\cdots,x_n^{-1} \pmod{p}$，其中 $p$ 是一个质数，不过允许离线，我们有一个 $O(\log p+n)$ 的算法。

先递推求出 $P_i=\prod\limits_{k=1}^{i} x_i$，那么可以用一次费马小定理求出 $P_n^{-1}\bmod p$。

然后考虑求出全体 $P_i$ 的逆元，可以得到 $P_i=P_{i+1}^{-1} x_{i+1}$。那么通过前缀乘积的逆元，我们很容易推导出 $x_i^{-1}=P_i^{-1}\cdot P_{i-1}$，由于模乘是 $O(1)$ 的，所以均摊到每一个元素就是 $O(\frac{\log p}{n})\sim O(1)$ 的了。

实际实现的话可以正着算一遍前缀乘积，然后倒着求一遍逆元，类似这样（以求质数逆元为例）：

buf[0] = 1;
for(int i=1;i<=tot;i++) buf[i] = M(buf[i - 1], pri[i]);
buf[tot] = I(buf[tot]);
for(int i=tot;i;i--){
    int p_inv = M(buf[i], buf[i - 1]);
    // 使用 p_inv 作为 p^-1 进行一点运算
    buf[i - 1] = M(buf[i], pri[i]);
}

Kinetic Tournament Tree (KTT)

EntropyIncreaser 引入 OI 界的一个很高明的科技，感觉挺实用但是例题非常少见。

先来考虑一个经典题（来自 Eric Zhang 的博客）：

你需要实现一个数据结构，用于维护 $n$ 个一次函数 $f_i(x)=a_ix_i+b_i$，同时有一个温度 $T$，初始时 $T=0$，支持以下操作：

• Update A：给定 $i,a'$，令 $a_i\gets a'$。
• Update B：给定 $i,b'$，令 $b_i\gets b'$。
• Query：给定 $[l,r]$，计算 $\max\limits_{i=l}^r f_i(T)$。
• Heaten：给定 $\Delta\geq 0$，令 $T\gets T+\Delta$。

最困难的操作无疑是 Heaten 操作，在温度升高时可能会影响决策，这非常麻烦。

Kinetic Tournamnet Tree 可以看成是势能线段树的扩展，我们给每一个节点维护一个一次函数表示该节点表示的区间，在当前温度下的最优函数，同时记录一个 $B$ 表示当温度升高 $B$ 时，该决策将不再是最优的。

那么当我们合并（pushup）的时候，只需要将左右儿子的函数的交点求出来，和左右儿子的 $B$ 取最小值就可以得到新的 $B$，左右儿子中截距较大的作为新的函数即可。

修改其实分成两种情况（假定已经到达了修改区间内的一个点）：

• 要求 $T\gets T+\Delta$ 但是 $\Delta\leq B$，就可以让 $\Delta\gets \Delta-B$，修改当前函数（我们其实只需要将一次函数右移，也就是令 $x\gets x+\Delta$），然后打一个标记就可以返回了。
• 如果不满足 $\Delta\leq B$，那么我们其实根本不知道最优决策是什么，只能向下递归。

查询就是线段树的基本操作，EntropyIncreaser 在他的博客中指出时间复杂度是均摊 $O(\log^3 n)$ 单次的，不过常数较小，近似于 $O(\log^2 n)$。

如果你觉得这个问题还是太弱了话，不妨看一个更加复杂的问题：

P5693 EI 的第六分块：区间加正数，区间询问最大子段和。$1\leq n,q\leq 4\times 10^5$，时间限制 $2\text{s}$。

如果改为加任意数，只有一个超级复杂的 $O((n+q)\sqrt{n})$ 做法（P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？），即所谓“第六分块”。

考虑如果是静态的，我们会有一个类似动态 dp 的做法，将矩阵展开可以看成每个点记录一个总和、最大后缀和、最大前缀和以及最大子段和。

总和维护最简单，正常线段树即可。剩余的三个操作都涉及到取 max，那我们考虑 KTT 去维护这个决策，这样就做到了 $O((n+q)\log^3 n)$。

给一个关键代码片段，可以看出非常好写：

struct line {
    i64 k, b;
    line(i64 k = 0, i64 b = 0) : k(k), b(b) {}
    i64 operator()(i64 x) const { return k * x + b; }
    line operator+(const line& rhs) const { return line(k + rhs.k, b + rhs.b); }
    line operator+(i64 x) const { return line(k, b + k * x); }
};

std::pair<line, i64> compare(line x, line y){
    if(x.k < y.k || (x.k == y.k && x.b < y.b)) std::swap(x, y);
    if(x.b >= y.b) return {x, inf};
    return {y, (x.b - y.b) / (y.k - x.k)};
}

struct node {
    line lmax, rmax, max, sum;
    i64 B;
} t[N << 2];
i64 tag[N << 2];

node operator+(const node& a, const node& b){
    auto [lmax, B1] = compare(a.lmax, a.sum + b.lmax);
    auto [rmax, B2] = compare(b.rmax, b.sum + a.rmax);
    auto [max_tmp, B3] = compare(a.max, b.max);
    auto [max_final, B4] = compare(max_tmp, a.rmax + b.lmax);
    return {lmax, rmax, max_final, a.sum + b.sum, std::min({a.B, b.B, B1, B2, B3, B4})};
}

void mktag(int i, i64 v){
    tag[i] += v, t[i].B -= v;
    t[i].lmax = t[i].lmax + v, t[i].rmax = t[i].rmax + v;
    t[i].max = t[i].max + v, t[i].sum = t[i].sum + v;
}

void pushdown(int i){
    if(tag[i]) mktag(ls, tag[i]), mktag(rs, tag[i]), tag[i] = 0;
}

void update(int ql, int qr, i64 v, int i, int l, int r){
    if(ql <= l && r <= qr && t[i].B >= v) return mktag(i, v);
    pushdown(i);
    if(ql <= mid) update(ql, qr, v, ls, l, mid);
    if(mid < qr) update(ql, qr, v, rs, mid + 1, r);
    t[i] = t[ls] + t[rs];
}

Min-Max 容斥与 gcd & lcm

Min-Max 容斥这个东西最近用的比较少，不过它的形式非常重要：

$$\begin{aligned} &\max(S)=\sum_{T\subseteq S,T\neq \varnothing}(-1)^{|T|+1}\min(T)\\ &\min(S)=\sum_{T\subseteq S,T\neq \varnothing}(-1)^{|T|+1}\max(T) \end{aligned}$$

这个东西和 $\gcd,\mathrm{lcm}$ 有什么关系呢？我们假设：

$$S_i=\prod_k p_k^{e_{ki}}$$

那么就有：

$$\begin{aligned} \mathrm{lcm}(S)&=\prod_k p_k^{\max\limits_i e_{ki}}=\prod_k p_k^{\sum\limits_{T\subseteq e_k} (-1)^{|T|+1} \min(T)}=\prod_k\prod_{T\subseteq e_k} \left(p_k^{\min(T)}\right)^{(-1)^{|T|+1}}\\ &=\prod_{T\subseteq S,T\neq \varnothing}\left(\prod_{k} p_k^{\min\limits_i e_{ki}}\right)^{(-1)^{|T|+1}}=\prod_{T\subseteq S,T\neq\varnothing} \gcd(T)^{(-1)^{|T|+1}} \end{aligned}$$

也就是：

$$\boxed{\mathrm{lcm}(S)=\prod_{T\subseteq S,T\neq\varnothing} \gcd(T)^{(-1)^{|T|+1}}}$$

这个形式的用处比较广泛，因为 $\gcd$ 通常可以用莫比乌斯反演处理，但是 $\mathrm{lcm}$ 只有在两个参数时才便于用莫比乌斯反演处理。我们不妨将它成为 lcm-gcd 反演。

考虑一道题：

(NOI 2025 联盟体第二次集训·曹杨二中场 T2) 给定 $n,m$，计算：

$$\prod_{(a_1,a_2,\cdots,a_m)\in [1,m]^n} \mathrm{lcm}(a)^{\gcd(a)}\pmod{998244353}$$

$1\leq n,m\leq 3\times 10^7$，时间限制为 $2\text{s}$。

看到多参 $\mathrm{lcm}$ 的形式，先应用刚刚得到的 lcm-gcd 反演公式：

$$\begin{aligned} &\prod_{(a_1,a_2,\cdots,a_n)\in [1,m]^n} \mathrm{lcm}(a)^{\gcd(a)}\\ &=\prod_{(a_1,a_2,\cdots,a_n)\in [1,m]^n}\left(\prod_{T\subseteq a,T\neq\varnothing} \gcd(T)^{(-1)^{|T|+1}}\right)^{\gcd(a)}\\ &=\prod_{(a_1,a_2,\cdots,a_n)\in [1,m]^n}\prod_{T\subseteq a,T\neq\varnothing} \gcd(T)^{(-1)^{|T|+1}\gcd(a)} \end{aligned}$$

为了方便，给原式取一个 $\log$ 得到：

$$\begin{aligned} &\sum_{(a_1,a_2,\cdots,a_n)\in [1,m]^n} \sum_{T\subseteq a,T\neq\varnothing} (-1)^{|T|+1}\gcd(a)\log(\gcd(T))\\ &=\sum_{(a_1,a_2,\cdots,a_n)\in [1,m]^n} \sum_{T\subseteq a,T\neq\varnothing}\sum_{d\mid a_i} \varphi(d) (-1)^{|T|+1}(\log(d)+\log(\gcd(T)))\\ &=\sum_{(a_1,a_2,\cdots,a_n)\in [1,m]^n} \sum_{T\subseteq a,T\neq\varnothing}\sum_{d\mid a_i} \varphi(d) (-1)^{|T|+1}\log(d)+\\&\sum_{(a_1,a_2,\cdots,a_n)\in [1,m]^n} \sum_{T\subseteq a,T\neq\varnothing}\sum_{d\mid a_i} \varphi(d) (-1)^{|T|+1}\log(\gcd(T)) \end{aligned}$$

于是我们将和式拆成了两个部分，先来考虑第一部分：

$$\begin{aligned} &\sum_{(a_1,a_2,\cdots,a_n)\in [1,m]^n} \sum_{T\subseteq a,T\neq\varnothing}\sum_{d\mid a_i} \varphi(d) (-1)^{|T|+1}\log(d)\\ &=\sum_{d=1}^{m}\varphi(d)\log(d)\sum_{(a_1,a_2,\cdots,a_n)\in [1,\left\lfloor\frac{m}{d} \right\rfloor]^n}\sum_{T\subseteq a, T\neq \varnothing} (-1)^{|T|+1}\\ &=\sum_{d=1}^{m}\varphi(d)\log(d)-\left\lfloor\frac{m}{d} \right\rfloor^n\sum_{T=1}^{n}\binom{T}{i}(-1)^{|T|}\\ &\sum_{d=1}^{m}\varphi(d)\log(d)\left\lfloor\frac{m}{d} \right\rfloor^n\cdot -((1-1)^{n}-1)\\ &=\sum_{d=1}^{m}\varphi(d)\log(d)\left\lfloor\frac{m}{d}\right\rfloor^n \end{aligned}$$

取 $\exp$ 得到：

$$\prod_{d=1}^{m}(d^{\varphi(d)})^{\left\lfloor\frac{m}{d}\right\rfloor^n}$$

然后考虑第二部分：

$$\begin{aligned} &\sum_{(a_1,a_2,\cdots,a_n)\in [1,m]^n} \sum_{T\subseteq a,T\neq\varnothing}\sum_{d\mid a_i} \varphi(d) (-1)^{|T|+1}\log(\gcd(T))\\ &=\sum_{d=1}^{m}\varphi(d)\sum_{(a_1,a_2,\cdots,a_n)\in [1,\left\lfloor \frac{m}{d} \right\rfloor]^n}\sum_{T\subseteq a,T\neq\varnothing} (-1)^{|T|+1}\sum_{\forall i\in T, k\mid i} \log(k)\sum_{\forall i\in T, x\mid \frac{i}{k}} \mu(x)\\ &=\sum_{d=1}^{m}\varphi(d)\sum_{k=1}^{\left\lfloor \frac{m}{d} \right\rfloor} \log(k)\sum_{T=1}^{n}(-1)^{|T|+1}\binom{n}{T}\sum_{\substack{(a_1,a_2,\cdots,a_T)\in [1, \lfloor\frac{m}{dk}\rfloor]^T\\ (b_1,b_2,\cdots,b_{n-T})\in [1,\left\lfloor \frac{m}{d} \right\rfloor]^{n-T}}} \sum_{\forall i\in a, x\mid i} \mu(x)\\ &=\sum_{d=1}^{m}\varphi(d)\sum_{T=1}^{n}(-1)^{|T|+1}\binom{n}{T}\left\lfloor \frac{m}{d} \right\rfloor^{n-T}\sum_{k=1}^{\left\lfloor \frac{m}{d} \right\rfloor} \log(k)\sum_{x=1}^{\left\lfloor \frac{m}{dk} \right\rfloor}\mu(x)\left\lfloor\frac{m}{dkx}\right\rfloor^{T}\\ &=\sum_{d=1}^{m}\varphi(d)\sum_{T=1}^{n}(-1)^{|T|+1}\binom{n}{T}\left\lfloor \frac{m}{d} \right\rfloor^{n-T}\sum_{E=1}^{\lfloor\frac{m}{d}\rfloor} \left\lfloor\frac{m}{dE}\right\rfloor^{T} \sum_{k\mid E} \log(k)\mu\left(\frac{E}{k}\right)\\ &=\sum_{d=1}^{m}\varphi(d)\sum_{E=1}^{\lfloor\frac{m}{d}\rfloor}\left(\sum_{k\mid E}\log(k)\mu\left(\frac{E}{k}\right)\right)\left(\sum_{T=1}^{n}(-1)^{|T|+1}\binom{n}{T}\left\lfloor\frac{m}{d}\right\rfloor^{n-T}\left\lfloor\frac{m}{dE}\right\rfloor^T\right)\\ &=\sum_{d=1}^{m}\varphi(d)\sum_{E=1}^{\lfloor\frac{m}{d}\rfloor}\left(\sum_{k\mid E}\log(k)\mu\left(\frac{E}{k}\right)\right)\left(-\sum_{T=1}^{n}\binom{n}{T}\left\lfloor\frac{m}{d}\right\rfloor^{n-T}\left(-\left\lfloor\frac{m}{dE}\right\rfloor\right)^T\right)\\ &=\sum_{d=1}^{m}\varphi(d)\sum_{E=1}^{\lfloor\frac{m}{d}\rfloor}\left(\sum_{k\mid E}\log(k)\mu\left(\frac{E}{k}\right)\right)\left(-\left(\left\lfloor\frac{m}{d}\right\rfloor - \left\lfloor\frac{m}{dE}\right\rfloor\right)^{n}+\left\lfloor\frac{m}{d}\right\rfloor^n\right) \end{aligned}$$

取 $\exp$ 得到：

$$\prod_{d=1}^{m}\left(\prod_{E=1}^{\lfloor\frac{m}{d}\rfloor} \left(\prod_{k\mid E} k^{\mu(\frac{E}{k})}\right)^{\left(-\left(\left\lfloor\frac{m}{d}\right\rfloor - \left\lfloor\frac{m}{dE}\right\rfloor\right)^{n}+\left\lfloor\frac{m}{d}\right\rfloor^n\right)}\right)$$

注意一下（2024 联赛模拟 T3 失落的圣剑）：

$$f(E)=\prod_{k\mid E}k^{\mu(\frac{E}{k})}=\begin{cases} p& E=p^k, k\in \mathbb{Z}_+,p\in\mathbb{P}\\ 1& \text{otherwise} \end{cases}$$

这个结论用数学归纳法证明是容易的，不过注意到其实有 $f(E)=e^{\Alpha(E)}$，其中 $\Alpha(E)$ 是 Mangoldt Function，根据 Mangoldt 函数的性质可以直接导出这个结论。

因此只需要处理处理预处理前缀所有形如 $p^k$ 的 $p$ 之乘积和前缀乘积的逆元，就可以在整除分块中快速计算中间那个积式，然后外面再套一层整除分块就可以求出整个式子。

OK 现在的难点是怎么快速求 $i^{\varphi(i)}$ 的前缀乘积，这个东西感觉怎么都要 $O(n\log n)$ 的样子。有很多方法，其中一个是分块打表，那个不优雅，有一个优雅的方法是 基于值域预处理的快速离散对数，明天学一下这个技术（实测如果没有这个东西，最大时间大约为 $5\text{s}$）。