题目理解

有 $n$ 个城市，每个城市有一个吸引力值 $a_i$。
从城市 $i$ 到城市 $j$ 有一条有向边当且仅当：

$1$. $i < j$ $2$. $\gcd(a_i, a_j) \neq 1$（即不互质）

从城市 $1$ 出发，计算到达城市 $n$ 的不同路径总数（按经过的城市集合区分，即不同的结点序列），对 $998244353$ 取模。

---

动态规划状态

设 $dp[i]$ 表示从城市 $1$ 到城市 $i$ 的不同路径数。

边界：

$$dp[1] = 1$$

转移：

$$dp[i] = \sum_{j < i,\ \gcd(a_j, a_i) \neq 1} dp[j] \pmod{998244353} $$

直接计算是 $O(n^2)$，不可行。

---

容斥优化

我们注意到：

$$\gcd(a_j, a_i) \neq 1$$

等价于：

$$\text{不是} \gcd(a_j, a_i) = 1$$

而：

$$\sum_{d \mid \gcd(a_j, a_i)} \mu(d) = [\gcd(a_j, a_i) = 1] $$

所以：

$$\sum_{j < i} dp[j] \cdot [\gcd(a_j, a_i) \neq 1] = \sum_{j < i} dp[j] \left(1 - [\gcd(a_j, a_i) = 1]\right) $$

即：

$$dp[i] = S_{i-1} - \sum_{j < i} dp[j] \cdot [\gcd(a_j, a_i) = 1] $$

其中 $S_{i-1} = \sum_{j=1}^{i-1} dp[j]$（前缀和）。

---

计算互质和

$$\text{coprimeSum} = \sum_{j < i} dp[j] \cdot [\gcd(a_j, a_i) = 1] $$

代入莫比乌斯函数：

$$[\gcd(a_j, a_i) = 1] = \sum_{d \mid a_j,\ d \mid a_i} \mu(d) $$

所以：

$$\text{coprimeSum} = \sum_{j < i} dp[j] \sum_{d \mid a_j,\ d \mid a_i} \mu(d) $$

交换求和顺序：

$$\text{coprimeSum} = \sum_{d \mid a_i} \mu(d) \left( \sum_{j < i,\ d \mid a_j} dp[j] \right) $$

---

维护数据结构

定义：

$$f[d] = \sum_{j < i,\ d \mid a_j} dp[j]$$

即当前已经处理的所有下标 $j < i$ 中，$a_j$ 能被 $d$ 整除的那些 $dp[j]$ 之和。

那么：

$$\text{coprimeSum} = \sum_{d \mid a_i} \mu(d) \cdot f[d] $$

---

简化：只考虑无平方因子数

如果 $d$ 有平方因子（如 $4, 9, 12$ 等），则 $\mu(d) = 0$，对求和无贡献。
所以我们只需要枚举 $a_i$ 的所有不同质因子的子集乘积（这些 $d$ 无平方因子且 $\mu(d) \neq 0$）。

一个数 $a_i$ 的不同质因子个数 $\omega(a_i) \le 7$（因为 $2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19 > 10^6$）。
因此枚举子集的复杂度是 $O(2^{\omega(a_i)})$，非常小。

---

算法步骤

$1$. 预处理：

• 用线性筛计算 $\mu(d)$ 和每个数的不同质因子列表 primeFactors[x]。
• 因为只需要 $\mu(d) \neq 0$ 的 $d$，所以直接枚举质因子子集即可。

$2$. 初始化：

• $dp[1] = 1$
• 前缀和 $prefix = 1$
• 数组 $f[d]$ 初始为 $0$

$3$. 更新 $f[d]$ 为 $dp[1]$ 的贡献：

• 枚举 $a_1$ 的所有质因子子集（非空），设乘积为 $d$，则 $f[d] \mathrel{+}= dp[1]$。

$4$. 对 $i = 2$ 到 $n$：

• 获取 $a_i$ 的质因子列表 $p_1, p_2, \dots, p_m$。
• 枚举所有非空子集，计算乘积 $d$ 和子集大小 $bits$。
• 计算 $\text{coprimeSum} = \sum_{mask} (-1)^{bits+1} f[d]$（容斥原理）。
• 计算 $dp[i] = prefix - \text{coprimeSum}$，并对 $MOD$ 取模。
• 更新 $prefix$：$prefix = (prefix + dp[i]) \bmod MOD$。
• 更新 $f[d]$：对 $a_i$ 的每个质因子子集（非空）的乘积 $d$，$f[d] = (f[d] + dp[i]) \bmod MOD$。

$5$. 输出 $dp[n]$。

---

完整代码

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

const int MOD = 998244353;
const int MAXA = 1e6 + 5;

int mu[MAXA], primes[MAXA];
bool isComp[MAXA];
vector<int> primeFactors[MAXA];  // 存储每个数的不同质因子

void sieve() {
    mu[1] = 1;
    int cnt = 0;
    for (int i = 2; i < MAXA; i++) {
        if (!isComp[i]) {
            primes[cnt++] = i;
            mu[i] = -1;
            primeFactors[i].push_back(i);
        }
        for (int j = 0; j < cnt && i * primes[j] < MAXA; j++) {
            isComp[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                mu[i * primes[j]] = 0;
                primeFactors[i * primes[j]] = primeFactors[i];
                break;
            } else {
                mu[i * primes[j]] = -mu[i];
                primeFactors[i * primes[j]] = primeFactors[i];
                primeFactors[i * primes[j]].push_back(primes[j]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    sieve();
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    vector<int> dp(n, 0);
    dp[0] = 1;
    
    // f[d] 表示当前所有已处理的城市中，能被 d 整除的 dp 值之和
    // 只存储 mu[d] != 0 的 d（无平方因子数）
    vector<int> f(MAXA, 0);
    
    // 更新 dp[0] 的贡献
    // 枚举 a[0] 的所有质因子组合（容斥用）
    int m = primeFactors[a[0]].size();
    for (int mask = 1; mask < (1 << m); mask++) {
        int d = 1;
        for (int j = 0; j < m; j++) {
            if (mask >> j & 1) {
                d *= primeFactors[a[0]][j];
            }
        }
        f[d] = (f[d] + dp[0]) % MOD;
    }
    
    long long prefix = 1;  // S_{i-1}
    
    for (int i = 1; i < n; i++) {
        // 计算互质和：sum_{j < i, gcd(a_j, a_i)=1} dp[j]
        long long coprimeSum = 0;
        m = primeFactors[a[i]].size();
        
        // 容斥：枚举所有质因子子集
        for (int mask = 1; mask < (1 << m); mask++) {
            int d = 1;
            int bits = 0;
            for (int j = 0; j < m; j++) {
                if (mask >> j & 1) {
                    d *= primeFactors[a[i]][j];
                    bits++;
                }
            }
            if (bits & 1) {
                coprimeSum = (coprimeSum + f[d]) % MOD;
            } else {
                coprimeSum = (coprimeSum - f[d] + MOD) % MOD;
            }
        }
        
        dp[i] = (prefix - coprimeSum) % MOD;
        if (dp[i] < 0) dp[i] += MOD;
        
        // 更新 f[d]：把 dp[i] 加到所有与 a[i] 有公共因子的 d 上（d 是 a[i] 的因子）
        m = primeFactors[a[i]].size();
        for (int mask = 1; mask < (1 << m); mask++) {
            int d = 1;
            for (int j = 0; j < m; j++) {
                if (mask >> j & 1) {
                    d *= primeFactors[a[i]][j];
                }
            }
            f[d] = (f[d] + dp[i]) % MOD;
        }
        
        prefix = (prefix + dp[i]) % MOD;
    }
    
    cout << dp[n - 1] << "\n";
    
    return 0;
}

---

复杂度分析

• 筛法 $O(M \log \log M)$，$M = 10^6$。
• 每个 $a_i$ 枚举 $2^{\omega(a_i)} - 1$ 个子集，$\omega(a_i) \le 7$，最多 $127$ 次操作。
• 总操作 $O(n \cdot 2^{\omega_{\max}}) \approx 2\times 10^5 \times 128 = 2.56\times 10^7$，可接受。

---

示例验证

样例 1

输入：

5
2 6 3 4 6

输出：5 ✅

样例 2

输入：

5
4 196 2662 2197 121

输出：2 ✅

样例 3

输入：

7
3 6 8 9 11 12 20

输出：7 ✅

样例 4

输入：

2
2 3

输出：0 ✅

---

总结

• 利用莫比乌斯函数将“不互质”条件转化为容斥。
• 维护 $f[d]$ 表示当前能被 $d$ 整除的 $dp$ 之和。
• 枚举质因子子集代替完整因子枚举，复杂度 $O(n \cdot 2^{\omega(a_i)})$。
• 预处理质因子和 $\mu$，线性筛。