题目理解

我们需要统计所有好数组的数量，其中：

• 数组元素取值范围：$[1, m]$
• 数组长度任意（非空）
• 定义 $f(k)$ 为所有长度为 $k$ 的子数组的最大值的 GCD
• 要求：对于所有 $1 \le i < j \le n$，有 $f(i) \ne f(j)$

关键观察

观察 $1$：$f(k)$ 的单调性

设 $s_k$ 为长度为 $k$ 的子数组的最大值序列，$g_k = \gcd(s_k)$。

注意到：

• $s_{k+1}$ 实际上是 $s_k$ 的相邻最大值序列
• $s_k$ 中的每个元素都能整除 $g_k$，因此 $g_k$ 整除 $g_{k+1}$

因此序列 $\{g_k\}$ 是严格递增的，且 $g_k$ 整除 $g_{k+1}$。

观察 $2$：长度限制

由于 $g_1 \ge 1$，且每次至少乘以 $2$（因为 $g_k < g_{k+1}$ 且 $g_k$ 整除 $g_{k+1}$），所以：

$$g_k \ge 2^{k-1}$$

又因为 $g_k \le m$，所以：

$$2^{k-1} \le m \Rightarrow k \le \lfloor \log_2 m \rfloor + 1 $$

因此数组长度最多为 $\lfloor \log_2 m \rfloor + 1$。

观察 $3$：非递减序列的特殊情况

考虑一个非递减序列 $a_1 \le a_2 \le \dots \le a_n$。

对于这个序列，长度为 $k$ 的子数组的最大值就是 $a_k, a_{k+1}, \dots, a_n$ 中的最大值？实际上更精确地说：长度为 $k$ 的子数组的最大值序列是 $[a_k, a_{k+1}, \dots, a_n]$（因为滑动窗口在非递减序列中，每个窗口的最大值就是窗口的最后一个元素）。

因此：

$$g_k = \gcd(a_k, a_{k+1}, \dots, a_n)$$

为了使所有 $g_k$ 不同，必须有 $a_1 < a_2 < \dots < a_n$（严格递增），否则会出现相等的后缀 $GCD$。

观察 $4$：排列计数

对于一个严格递增的序列 $a_1 < a_2 < \dots < a_n$，考虑它的所有排列。

从 $s_n$ 开始：$s_n = [a_n]$（只有最后一个元素）。

要得到 $s_{n-1}$，我们需要在序列中插入 $a_{n-1}$，使得相邻最大值序列变为 $s_n$。经过分析，有 $2$ 种方式：

• 放在 $a_n$ 前面：$[a_{n-1}, a_n]$
• 放在 $a_n$ 后面：$[a_n, a_{n-1}]$

类似地，对于 $a_k$，也有 $2$ 种插入方式。因此，一个严格递增序列共有 $2^{n-1}$ 个好排列。

$DP$ 状态设计

设 $dp[i][g]$ 表示：以 $i$ 作为第一个元素的严格递增序列中，整个数组的 GCD 恰好为 $g$ 的序列数量（乘以对应的 $2^{\text{长度}-1}$ 系数）。

但这样状态太多，我们需要优化。

优化 $1$：合并长度维度

由于我们在转移时会乘以 $2$，可以直接在 $DP$ 中处理这个系数。

设 $f_i(g)$ 表示：以 $i$ 作为第一个元素，且整个数组 GCD 恰好为 $g$ 的序列的权重和，其中权重为 $2^{\text{长度}-1}$。

对于长度为 $1$ 的序列：$[i]$，权重为 $2^{0} = 1$，GCD 为 $i$。

对于长度 $>1$ 的序列：假设我们已知以某个 $j > i$ 开头、$GCD$ 为 $h$ 的序列权重和为 $S$，那么在这些序列前加上 $i$ 后：

• 新序列的 $GCD$ 变为 $\gcd(i, h)$
• 长度增加 $1$，权重乘以 $2$

因此转移公式：

$$f_i(\gcd(i, h)) \mathrel{+}= 2 \times (\text{所有以 } j>i \text{ 开头、GCD 为 } h \text{ 的序列权重和}) $$

优化 $2$：利用约数关系

令 $sum_h = \sum_{j > i} f_j(h)$，即所有大于 $i$ 的开头元素、GCD 恰好为 $h$ 的序列权重和。

对于固定的 $i$，我们需要对每个 $h$，将 $2 \cdot sum_h$ 加到 $f_i(\gcd(i, h))$ 上。

直接枚举所有 $h$ 会超时，但注意到 $\gcd(i, h)$ 一定是 $i$ 的约数，所以只需要关心 $i$ 的约数。

对于 $i$ 的一个约数 $g$，我们需要知道：对于所有满足 $\gcd(i, h) = g$ 的 $h$，$sum_h$ 的总和。

优化 $3$：容斥原理

对于 $i$ 的约数 $g$，定义：

$$U_g = \sum_{g \mid h} sum_h$$

即所有 $h$ 是 $g$ 的倍数的 $sum_h$ 之和。

那么，所有满足 $g \mid \gcd(i, h)$ 的 $h$ 对应的 $sum_h$ 之和就是 $U_g$。

而满足 $\gcd(i, h) = g$ 的条件等价于：$g \mid \gcd(i, h)$ 且对于 $i$ 的任何大于 $g$ 的约数 $g'$，$g' \nmid \gcd(i, h)$。

通过容斥原理：

$$\sum_{\gcd(i, h) = g} sum_h = U_g - \sum_{\substack{g' \mid i \\ g' > g \\ g \mid g'}} \sum_{\gcd(i, h) = g'} sum_h $$

更具体地，设 $divs$ 为 $i$ 的所有约数（从小到大排序），对于 $divs$ 中的 $g$，从大到小计算：

$$cnt_g = U_g - \sum_{\substack{g' \in divs \\ g' > g \\ g \mid g'}} cnt_{g'} $$

这样，$cnt_g$ 就是所有满足 $\gcd(i, h) = g$ 的 $h$ 对应的 $sum_h$ 之和。

然后：

$$f_i(g) = 2 \cdot cnt_g$$

另外，单独的长度为 $1$ 的序列也要考虑：$f_i(i) \mathrel{+}= 1$。

算法实现

$1$. 预处理所有数的约数 $2$. 从 $i = m$ 向下遍历到 $1$：

• 对 $i$ 的每个约数 $g$，计算 $cnt_g$（容斥）
• 设置 $f_i(g) = 2 \cdot cnt_g$
• $f_i(i) \mathrel{+}= 1$（长度为 $1$ 的序列）
• 将 $f_i(g)$ 累加到答案中
• 更新 $sum$ 数组：对于 $i$ 的每个约数 $g$ 的每个约数 $d$，$sum_d \mathrel{+}= f_i(g)$

时间复杂度

$$O\left(\sum_{i=1}^m \sigma(i)^2\right)$$

其中 $\sigma(i)$ 是 $i$ 的约数个数。对于 $m \le 10^5$，这个复杂度是可接受的。

完整代码

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 9, mod = 998244353;
using ll = long long;

int add(int a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
    return a;
}

// dp[i] = 以 i 开头的序列，GCD 恰好为某个值的权重和
// 但这里我们用滚动的方式：cur 存储当前 i 的 f_i(g)
// sum[g] 存储所有 j > i 中，GCD 为 g 的倍数的序列权重和
int dp[N], cur[N], uni[N];
int sum[N];
vector<int> d[N];

void solve() {
    int m; 
    cin >> m;
    
    // 初始化
    for (int i = 1; i <= m; i++) {
        dp[i] = cur[i] = 0;
        uni[i] = 0;
        sum[i] = 0;
    }
    
    int ans = 0;
    
    // 从大到小枚举第一个元素
    for (int i = m; i >= 1; i--) {
        // 清空当前 i 的 cur 值
        for (int j : d[i]) {
            cur[j] = 0;
        }
        
        int sz = d[i].size();
        
        // 容斥计算 cnt_g
        for (int idj = sz - 1; idj >= 0; idj--) {
            int j = d[i][idj];
            // uni[j] 初始为所有 j 的倍数的 sum 之和的两倍
            uni[j] = add(sum[j], sum[j]);
            // 减去更大的约数贡献
            for (int idk = idj + 1; idk < sz; idk++) {
                int k = d[i][idk];
                if (k % j == 0) {
                    uni[j] = add(uni[j], -uni[k]);
                }
            }
            // cur[j] = 2 * cnt_j - 已有的 dp[j] 贡献
            cur[j] = add(uni[j], -add(dp[j], dp[j]));
        }
        
        // 长度为 1 的序列 [i]
        cur[i] = add(cur[i], 1);
        
        // 更新答案和 sum 数组
        for (int j : d[i]) {
            dp[j] = add(dp[j], cur[j]);
            for (auto k : d[j]) {
                sum[k] = add(sum[k], cur[j]);
            }
            ans = add(ans, cur[j]);
        }
    }
    
    cout << ans << '\n';
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    // 预处理所有数的约数
    for (int i = 1; i < N; i++) {
        for (int j = i; j < N; j += i) {
            d[j].push_back(i);
        }
    }
    
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

代码解释

$1$. 预处理：d[i] 存储 $i$ 的所有约数

$2$. 核心循环：从 $i = m$ 到 $1$ 枚举第一个元素

• 对于 $i$ 的每个约数 $j$，通过容斥计算 $\sum_{\gcd(i, h) = j} sum_h$
• $cur[j] = 2 \times cnt_j - 2 \times dp[j]$（减去之前已经统计过的）
• 加上长度为 $1$ 的序列：cur[i] += 1
• 更新 dp[j] 和 sum[k]（$k$ 是 $j$ 的约数）

$3$. sum[g] 的含义：所有 $j > i$ 中，GCD 恰好为 $g$ 的倍数的序列权重和

$4$. 答案累加：每次计算完 cur[j] 后加到答案中

示例验证

对于 $m = 2$：

• $[1]$：长度 $1$，权重 $1$
• $[2]$：长度 $1$，权重 $1$
• $[1,2]$：长度 $2$，权重 $2^{1}=2$
• $[2,1]$：长度 $2$，权重 $2^{1}=2$

总和 $1+1+2+2=6$？但样例输出是 $4$。

等等，这里需要重新检查。实际上题目要求的是数组的个数，不是权重和。我们的权重 $2^{\text{长度}-1}$ 正是每个严格递增序列对应的好排列数。所以：

• 严格递增序列 $[1]$：对应 $1$ 个数组 $[1]$
• 严格递增序列 $[2]$：对应 $1$ 个数组 $[2]$
• 严格递增序列 $[1,2]$：对应 $2$ 个排列 $[1,2]$ 和 $[2,1]$

总数 $1+1+2=4$，与样例一致。