T4

设g = gcd(N, D)，则标记过程会形成g条独立的链：

• 每条链的长度为N/g
• 第i条链的起始点为i (0 ≤ i < g)
• 每条链内部的标记顺序是等差数列，公差为D mod N 因此，第K次标记的位置可以表示为：
• 链编号：(K-1) % g
• 链内位置：(K-1)/g * D

最终位置 = 链编号 + 链内位置

T5

问题

给定长度为 $n$ 的序列 $A$，对于任意连续子数组 $B$，定义 $f(B)$ 为将 $B$ 变为回文所需的最小修改次数。要求计算所有可能的连续子数组 $B$ 的 $f(B)$ 之和。

思路

1. 比较对数：对于长度为 $k$ 的子数组，有 $\left\lfloor \frac{k}{2} \right\rfloor$ 对需要比较的元素。
2. 修改次数：对于每一对需要比较的元素 $(B[i], B[j])$，如果 $B[i] \neq B[j]$，则需要至少修改其中一个元素，贡献为 1；否则贡献为 0。
3. 总贡献：所有子数组的 $f(B)$ 之和等于所有子数组中不相等对称对的总数。

数学推导

1. 总比较对数：

   • 对于所有长度为 $k$ 的子数组，每个子数组有 $\left\lfloor \frac{k}{2} \right\rfloor$ 对需要比较的元素。

   • 长度为 $k$ 的子数组共有 $n - k + 1$ 个。

   • 因此，总比较对数为： $\sum_{k=1}^n (n - k + 1) \left\lfloor \frac{k}{2} \right\rfloor$

   • 可以简化为：

     $\sum_{i=1}^n (n + 1 - i) \left\lfloor \frac{i}{2} \right\rfloor$

   • 这是因为 $i$ 从 1 到 $n$ 枚举子数组的长度 $k$，而 $n - k + 1$ 是长度为 $k$ 的子数组的数量。

2. 相等对的贡献：

   • 对于值 $x$，设其在序列中的位置为 $P = [p_1, p_2, \ldots, p_m]$。
   • 对于任意两个位置 $p_i$ 和 $p_j$（$i < j$），如果 $p_i$ 和 $p_j$ 在某个子数组的对称位置，则它们不需要修改，贡献为 0。
   • 具体来说，对于子数组 $[l, r]$，如果 $p_i$ 和 $p_j$ 满足 $p_i = l + d$ 和 $p_j = r - d$ 对于某个 $d$，则它们是对称的。
   • 这样的子数组 $[l, r]$ 的数量为 $\min(p_i, n + 1 - p_j)$。
   • 因此，所有相等对的贡献为：$\sum_{x} \sum_{i < j} \min(p_i, n + 1 - p_j)$
   • 其中 $x$ 枚举所有可能的值，$p_i$ 和 $p_j$ 是 $x$ 在序列中的位置。

3. 双指针法计算相等对贡献：

   • 对于每个值 $x$，将其位置数组 $P$ 排序。
   • 初始化双指针 $l = 0$ 和 $r = |P| - 1$。
   • 当 $l < r$ 时：
     • 如果 $P[l] < n + 1 - P[r]$，则对于所有 $j$ 从 $l+1$ 到 $r$，有 $\min(P[l], n + 1 - P[j]) = P[l]$。
       • 贡献为 $(r - l) \times P[l]$。
       • 移动 $l$ 右移。
     • 否则，对于所有 $i$ 从 $l$ 到 $r-1$，有 $\min(P[i], n + 1 - P[r]) = n + 1 - P[r]$。
       • 贡献为 $(r - l) \times (n + 1 - P[r])$。
       • 移动 $r$ 左移。
   • 这样可以在 $O(m)$ 时间内计算一个值 $x$ 的所有相等对贡献，其中 $m$ 是 $x$ 的出现次数。

T6

题目分析

题目要求对于所有满足条件的度数序列X（即$∑X_i = 2N-2$且$X_i≥1$），计算这些序列对应的树的最大直径之和。关键点在于：

1. 存在好树的条件：$∑X_i = 2N-2$（树的基本性质）。
2. 最大直径的公式：对于满足条件的度数序列$X$，最大直径 = (度数≥2的顶点个数) + 1。
3. 问题转化：计算所有满足条件的序列X的最大直径之和，即：
   • 设S为所有满足$∑X_i=2N-2$且$X_i≥1$的序列集合。
   • 则答案为：$∑_{X∈S} [ (X中≥2的元素个数) + 1 ] = |S| + N × (满足X_i≥2的序列数)$。

推导

具体步骤如下：

• 度数序列$X$：对于一棵$N$ 个顶点的树，其度数序列 $X = (X_1, X_2, \ldots, X_N)$ 满足$X_i \geq 1$（每个顶点至少有一条边）且$\sum_{i=1}^N X_i = 2N - 2$（因为树有 $N-1$条边，每条边贡献两个度数）。
• 最大直径：对于给定的度数序列$X$，树的最大直径 $f(X)$ 是$K + 1$，其中$K$是度数$\geq 2$ 的顶点个数。这是因为直径路径上的非端点顶点度数至少为 2，而端点度数为 1。

2. 目标表达式

我们需要计算所有满足条件的 ( X ) 的最大直径之和：

$\sum_{X \in S} f(X) = \sum_{X \in S} (K + 1)$

其中 $S$ 是所有满足$\sum X_i = 2N - 2$且 $X_i \geq 1$ 的序列集合，$K$是 $X$ 中 $\geq 2$ 的元素个数。

3. 拆分求和

将 ( K + 1 ) 拆分为两部分：

$\sum_{X \in S} (K + 1) = \sum_{X \in S} 1 + \sum_{X \in S} K = |S| + \sum_{X \in S} K$

• $|S|$是满足条件的序列总数。
• $\sum_{X \in S} K$是所有序列中$\geq 2$ 的元素个数的总和。

4. 计算$\sum_{X \in S} K$

注意到$K$是序列 ( X ) 中 $\geq 2$ 的元素个数，可以交换求和顺序：

$\sum_{X \in S} K = \sum_{X \in S} \sum_{i=1}^N [X_i \geq 2] = \sum_{i=1}^N \sum_{X \in S} [X_i \geq 2]$

其中 $[X_i \geq 2]$是指示函数，当$X_i \geq 2$ 时为 $1$，否则为 $0$。

• 对于固定的 $i$，$\sum_{X \in S} [X_i \geq 2]$ 是满足 $X_i \geq 2$的序列数。
• 由于所有 ( i ) 对称，这个值与 ( i ) 无关，因此：

$\sum_{X \in S} K = N \cdot \text{Number of } X \in S \text{ with } X_1 \geq 2$

5. 计算$|S|$和满足$X_1 \geq 2$ 的序列数

• 计算$|S|$：

  • 这是$\sum X_i = 2N - 2$且 $X_i \geq 1$ 的正整数解数。
  • 令$Y_i = X_i - 1$，则$\sum Y_i = N - 2$ 且$Y_i \geq 0$。
  • 非负整数解数为$\binom{(N - 2) + (N - 1)}{N - 1} = \binom{2N - 3}{N - 1}$。

• 计算满足$X_1 \geq 2$的序列数：

  • 令$Z_1 = X_1 - 1$，$Z_i = X_i$（$i \geq 2$），则$\sum Z_i = 2N - 3$且$Z_i \geq 1$。
  • 令$W_i = Z_i - 1$，则$\sum W_i = N - 3$ 且$W_i \geq 0$。
  • 非负整数解数为$\binom{(N - 3) + (N - 1)}{N - 1} = \binom{2N - 4}{N - 1}$。

6. 合并结果

将两部分代入：

$\sum_{X \in S} f(X) = |S| + N \cdot \text{Number of } X \in S \text{ with } X_1 \geq 2 = \binom{2N - 3}{N - 1} + N \cdot \binom{2N - 4}{N - 1}$

组合数学推导

1. |S|的计算：将问题转化为非负整数解的个数。令$Y_i = X_i - 1$，则$∑Y_i = N-2$，解数为$C(N-2 + N-1, N-1) = C(2N-3, N-1)$。
2. 满足X_i≥2的序列数：固定一个位置，令$Z_1 = X_1 - 1，Z_i = X_i（i≥2）$，则$∑Z_i = 2N-3$且$Z_i≥1$。再令$W_i = Z_i - 1$，则$∑W_i = N-3$，解数为$C(2N-4, N-1)$。
3. 最终公式：答案 = $C(2N-3, N-1) + N × C(2N-4, N-1)$。