好题题解整理（四）

发表于 更新于 分类于 阅读次数：

重操旧业。

agc049e Increment Decrement

对于一个非负整数序列，我们可以做两个操作：

  1. 选定一项令其加一或减一，代价为 \(1\) 。
  2. 选定一个区间令其中每一项同时加一或同时减一，代价为 \(C\) 。

定义一个非负整数序列的代价为从一个全 0 序列操作得到该序列所需要花费的最小代价。

先给定 \(N\) 和 \(K\) 以及一个 \(N \times K\) 的非负整数矩阵 \(B\) ，依次将每个 \(A_i\) 赋值为 \(B_{i,1}, B_{i,2} ... B_{i,K}\) ，求所有 \(K^N\) 个可能的 \(A\) 序列的代价的和。

时间复杂度：\(O(N^2 K (K + C))\) 。

题解

子问题引入

先来考虑对于给定的长度为 \(N\) 的序列 \(A\) ，如何求出 \(A\) 的代价？

不妨先进行所有 2 操作得到序列 \(D\) ，然后对 \(D\) 执行 1 操作得到 \(A\) ，如果 \(D\) 确定的话两个操作的代价都是容易求的，总代价即（默认 \(D_0 = 0\)）：

\[ \sum_{i=1}^N C \max(D_i - D_{i-1}, 0) + |A_i - D_i| \]

据此不难想到一个 DP ，设 \(f_{i,j}\) 表示钦定 \(D_i = j\) 的前提下上式前 \(i\) 项的最小值，转移有

\[ f_{i,j} = \min_{k \ge 0} (f_{i-1,k} + C \max(j - k, 0) + |j - A_i|) \]

设 \(F_i(x) = f_{i,x}\) ，接下来我们证明，\(F_i(x)\) 总是凸函数（离散意义上）。

凸性证明

采用数学归纳法，对于 \(i = 0\) ，我们不妨令 \(F_0(x) = (C + 1) x\) 。

设 \(G(x) = F_i(x) - |x - A_i|\) ，如果 \(G(x)\) 是凸的，由于 \(|x - A_i|\) 也是凸的，就可以证明 \(F_i(x)\) 是凸的。

\(F_{i-1}(x)\) 最小值取在 \(x = k\) 。那么首先显而易见的是：

\[ \forall x \in [0, k], G(x) = F_{i-1}(k) \]

设 \(x_0\) 是最大的满足 \(G(x_0) - G(x_0 - 1) < C\) 的值，那么可以发现

\[ \forall x \in [k + 1, x_0], G(x) = F_{i-1}(x) \]

对于 \(x > x_0\) 的部分，由于 \(F_{i-1}(x)\) 增长过快，最优的转移点就不会变了，因此

\[ \forall x \ge x_0 + 1, G(x) = F_{i-1}(x_0) + C (x - x_0) \]

那么 \(G(x)\) 被分为三个部分，第一部分是斜率为 \(0\) 的折线，第二部分基于归纳假设是凸的斜率在 \([1, C - 1]\) 内的折线，第三部分是斜率为 \(C\) 的折线，因此 \(G(x)\) 是凸的，\(F_i(x)\) 也是凸的。

问题简化

注意到 \(G(x)\) 是一个折线，由斜率从 \(0\) 到 \(C\) 的线段依次组成，这意味着折线的端点至多有 \(C\) 个，不妨设 \(X_i\) 表示斜率为 \(i\) 的线段的起点横坐标，我们考虑通过维护 \(X_i\) 来间接维护 \(G(x)\) 所代表的折线。

首先我们要支持在 \(G(x)\) 上加上 \(|x - A_i|\) ，可以发现这个操作后，\(A_i\) 左侧的直线都减小了 \(1\) ，\(A_i\) 右侧的直线都增加了 \(1\) ，这其实就是在 \(X\) 序列里添加两个 \(A_i\) 。

紧跟着我们要把 \(G(x)\) 进行一次转移，也就是按照前面所说的分成三段，第一段就是把斜率为 \(-1\) 的直线调整为斜率为 \(0\) ，第二段不变，第三段是把斜率为 \(C+1\) 的直线调整为斜率为 \(C\) 。那么事实上，这就是在 \(X\) 序列里头删掉最小值和最大值。

而每次查询 \(G(x)\) 的最小值的位置，也就是每次被删掉的最小值。

综上所述，求一个序列 \(A\) 的代价的过程可以被描述为：

  1. 建立一个可重集 \(S\) ，包含 \(C\) 个 \(0\) 。
  2. 从小到大对于每个 \(i\) ，将两个 \(A_i\) 放入 \(S\) 中，将答案加上 \(A_i - \min S\) ，然后删除 \(S\) 中的最小值和最大值

DP 计数

现在回到原问题，怎么记数。

不妨对于每个值 \(x\) ，求出它在 \(S\) 中作为最小值被删去的次数 \(tot(x)\) 。枚举值 \(x\) ，由于只关注大小，不妨把小于 \(x\) 的数都看做 \(0\) ，不小于 \(x\) 的数都看做 \(1\) ，这样一来 \(S\) 中始终只有 \(0\) 和 \(1\) ，可以用 \(1\) 的数量表示 \(S\) 。设 \(h_{i,j}\) 表示考虑刚加入两个 \(A_i\) 时 \(S\) 中有恰好 \(j\) 个 \(1\) 的方案数，然后不难算出

\[ \sum_{i=0}^{x-1} tot(i) = \sum_{i=1}^N \sum_{j=0}^{C+1} h_{i,j} = K^N - \sum_{i=1}^N h_{i,C+2} \]

最后答案即

\[ \sum_{i=1}^N \sum_{j=1}^K (K^{N-1} - tot(B_{i,j})) B_{i,j} \]

pe214 Totient Chains

定义数论函数 \(f\) 满足：

\[ f(x) = \begin{cases} 1, & x = 1 \\ f(\varphi(x)) + 1, & x > 1 \end{cases} \]

给定 \(n, a\) ，对于 \([1, m]\) 内的每个整数 \(k\) ，求出有多少个数 \(x\) 满足：

  1. \(f(x) = k\)
  2. \(x\) 的每个质因子不超过 \(n\) 。
  3. \(x\) 的标准分解中的每个质因子的指数不超过 \(a\) 。

时间复杂度：\(O(n + m \log m \log n)\) 。

主观难度：8 / 12

题解

\(f(x)\) 其实就是 \(x\) 一直迭代欧拉函数迭代的次数。注意到如果 \(x > 2\) ，那么 \(\varphi(x)\) 一定是偶数。

证明：设 \(x = 2^s t, t \bmod 2 = 1\) 。若 \(t = 1\) 则 \(s > 1\) 则 \(2 \mid \varphi(x) = 2^{s-1}\) ；若 \(t > 1\) 则存在奇质数 \(p \mid x\) 则 \(2 \mid p - 1 \mid \varphi(x)\) 。


把迭代欧拉函数的过程抽象到图上，\(x\) 每整除一次质数 \(p\) ，就在节点 \(p\) 上放一个棋子。质数 \(p\) 的后继是 \(p - 1\) 的每个质因子。那么迭代一次就相当于把每个节点上的一个棋子向每个后继移动。

由于迭代一次后 \(2\) 节点必然有棋子，且迭代的过程中该节点始终有棋子。因此可以认为当 \(2\) 节点没有棋子的时候迭代结束。注意到每次迭代 \(2\) 节点都只会有一个棋子被删去。也就是说，迭代的次数就是 \(2\) 节点曾拥有的棋子数。

具体地，设 \(g(x)\) 表示迭代的过程中有多少棋子经过 \(2\) 节点，那么：

\[ g(x) = \begin{cases} 0, & x = 1 \\ g(\varphi(x)), & x > 1 \land x \bmod 2 = 1 \\ g(\frac{x}{2}) + 1, & x \bmod 2 = 0 \end{cases} \]

并且

\[ \begin{cases} f(x) = g(x) + 2, & x > 1 \land x \bmod 2 = 1 \\ f(x) = g(x) + 1, & x = 1 \lor x \bmod 2 = 0 \end{cases} \]

那么我们只需要根据奇对奇数和偶数分别计算有多少数满足 \(g(x) = k\) 即可。而容易发现，对于标准分解 \(x = \prod p_i^{k_i}\) 有

\[ g(x) = \sum_i k_i g(p_i) \]

那么问题就转化为背包问题，设 \(d(i, j)\) 表示通过前 \(i\) 个质数组成的 \(g(x) = j\) 的数有多少，转移为

\[ d(i, j) = \sum_{k=0}^a d(i - 1, j - k \times g(p_i)) \]

暴力计算的复杂度为 \(O(n m a)\) ，可以前缀和优化做到 \(O(n m)\) 。

构造普通生成函数 \(D_i (s) = \sum d(i, j) s^j\) ，那么转移式等价于 \(D_i (s) = D_{i-1} (s) \sum_{k=0}^a s^{k g(p_i)}\) 。也就是说我们要计算的实际上是下面这个多项式：

\[ D(s) = \prod_i \sum_{k=0}^a s^{k g(p_i)} \]

虽然 FFT 优化多项式乘法的复杂度劣于直接前缀和优化，但是根据 \(g(x)\) 的定义可以得知 \(g(x) \le \log_2 x\) ，不妨把 \(g\) 值相同的质数放在一起，设 \(t_x\) 表示有多少 \(n\) 以内的质数 \(p\) 满足 \(g(p) = x\) ，那么

\[ D(s) = \prod_x (\sum_{k=0}^a s^{k x})^{t_x} = \prod_x (\frac{1 - s^{x (a + 1)}}{1 - s^x})^{t_x} \]

按照上式计算 \(D(s) \bmod x^{m+1}\) 的复杂度即 \(O(m \log m \log n)\) 。

另外形如 \(\alpha_t (s) = (1 - s)^t\) 的多项式对任意的整数 \(t\) （可以为负）都是可以用组合数表示每一项系数的，因此仅仅需要多项式乘法，而不需要求逆和快速幂。

pe219 Skew-cost coding

定义一个 01 串的集合 \(S\) 是合法的，当且仅当：

  1. \(|S| = n_0\)
  2. \(\forall a, b \in S, a \neq b\)：\(a\) 不是 \(b\) 的前缀。

设 \(S\) 内所有串中 \(0, 1\) 的个数分别为 \(s_0, s_1\) ，则 \(S\) 的代价定义为 \(a \times s_0 + b \times s_1\) 。求所有合法的集合的最小代价和。

时间复杂度：\(O((a + b)^3 \log n)\) 。

主观难度：6 / 12

题解

首先不难设计出一个 DP ，设 \(f(n)\) 表示 \(|S| = n\) 的答案，则有

\[ f(n) = \min_{k=1}^{n-1} \{f(k) + k a + f(n - k) + (n - k) b\} \]

注意到对于 \(C(n) = \min \{A(k) + B(n-k)\}\) 如果 \(A, B\) 都是凹函数，那么 \(C\) 也一定是凹函数，并且可以通过闵科夫斯基和线性计算 \(C\) 。这里我们可以归纳地证明，\(f\) 恰是一个凹函数：

假设 \(f(n)\) 在 \(n \in [1, N]\) 是凹函数，那么 \(f_a(n) = f(n) + n a\) 和 \(f_b(n) = f(n) + n b\) 在 \(n \in [1, N]\) 都是凹函数，由于 \(f(N + 1)\) 的值可以由 \(f_a(n)\) 和 \(f_b(n)\) 在 \(n \in [1, N]\) 的取值确定，那么可以知道 \(f(n)\) 在 \([1, N + 1]\) 也是凹函数。


于是利用闵科夫斯基和的方法就可以 \(O(n)\) 求出 \(f(1)\) 到 \(f(n)\) 的值。当然这是不够的。

考虑计算 \(f\) 的差分数组的和。设 \(g(x)\) 是满足 \(f(n + 1) - f(n) = x\) 的 \(n\) 的数量，\(S_g(x) = \sum_{y=1}^x g(y)\) 。

我们可以找到最大的 \(m\) 满足 \(S_g(m) < n - 1\) ，那么要求的答案即

\[ (\sum_{x=1}^m x \times g(x)) + (m + 1) (n - 1 - S_g(m)) \]

设 \(h(x) = x g(x), S_h(x) = \sum_{y=1}^x h(y)\) ，上式即 \(S_h(m) + (m + 1) (n - 1 - S_g(m))\) ，要计算 \(S_h (m)\) 和 \(S_g(m)\) ，显然是可以矩阵快速幂的：

\[ \begin{aligned} g(x) &= g(x - a) + g(x - b) \\ S_g(x) &= S_g(x - 1) + g(x) \\ h(x) &= h(x - a) + h(x - b) + a \times g(x - a) + b \times g(x - b) \\ S_h(x) &= S_h(x - 1) + h(x) \end{aligned} \]

问题只剩下求 \(m\) ，倍增加矩阵乘法即可。

cc-hotmeals Hot Meals and Queues

如果有 \(n\) 个人依次排队，第 \(i\) 个人可以选择 \(i + 1\) 个位置插入，如果不是插在最后面，则称为插队，插队会使其后面的人的愤怒值加一。\(n\) 个人排完队后，按照位置从前到后的顺序的人的愤怒值组成的序列称为愤怒值序列。

现在维护一个长为 \(N\) 的序列 \(\{a\}\) ，有 \(M\) 次操作：

  1. 给定一个区间，求以该区间作为愤怒值序列的话，其对应的排队方式中有多少人插队。
  2. 给定一个区间和参数 \(x\) ，区间内每个数加上 \(x\) 。

时间复杂度：\(O(N + M \log^2 N)\) 。

主观难度：6 / 12

题解

对于愤怒值序列 \(\{b\}\) ，考虑最后一个值 \(b_n = x\) ，排在最后的人的愤怒值为 \(x\) ，说明它是第 \(n - x\) 个排队的人，并且后面 \(x\) 个人全都插队了。

那么如果考虑按排队顺序的人的是否插队组成的 01 序列 \(\{c\}\) 的话，在 \(b\) 的尾端加一个 \(x\) ，等价于：

  1. 把 \(c\) 分为左右两部分，其中右半部分长为 \(x\) 。
  2. 把右半部分的值都变为 \(1\) 。
  3. 在两部分中间插入一个 \(0\) 。

考虑 \(c\) 中 \(0\) 的个数，容易发现一个位置如果为 \(0\) ，当且仅当它插入至 \(c\) 后，后来插入的数都在其右边。也就是说，序列 \(b\) 的第 \(i\) 个数最终是未插队的，当且仅当

\[ \forall j > i \;\; b_j < b_i + j - i \]

即

\[ \forall j > i \;\; b_j - j < b_i - i \]

对于序列 \(a_i - i\) ，我们要查询的就是区间内后缀最大值的数量。

用线段树维护，每个节点记录区间内后缀最大值的数量和区间最大值。我们只需要实现函数 \(Q(u, x)\) 表示查询 \(u\) 节点内大于 \(x\) 的后缀最大值的数量，分三种情况讨论，一种是 \(u\) 是叶子，一种是大于 \(x\) 的后缀最大值全在左儿子区间内，还有一种是有一部分在右儿子区间内。容易发现后两种情况都只需要调用一个儿子的 \(Q\) 函数，因此 \(Q\) 函数的时间复杂度是 \(O(\log N)\) 的。利用 \(Q\) 函数即可以实现线段树节点的更新和线段树查询。