P14035 [PAIO 2025] GCD

**DO NOT** include `gcd.h`. Submit using C++ >=17.

给定一个长度为 $N$ 的整数序列 $A[1], A[2], \dots, A[N]$。另给定两个整数 $K$ 和 $V$。 设 $\text{gcd}(X_1, X_2, \dots, X_k)$ 表示整数 $X_1, X_2, \dots, X_k$ 的最大公约数。例如，$\text{gcd}(14, 21) = 7$，$\text{gcd}(4, 8, 15) = 1$。 定义函数 $f_{l,r}(x) = \text{gcd}(A[1], A[2], \dots, A[l], A[r], \dots, A[N])^K \oplus x$，其中 $\oplus$ 表示按位异或运算。你的任务是计算如下和： $$ \left(\sum_{x=0}^{V} \sum_{l=1}^{N} \sum_{r=l+1}^{N} f_{l,r}(x) \cdot (A[l] + A[r])\right) \bmod 998\,244\,353 $$ ### 实现细节 你需要完成名为 `calculate_sum` 的函数： ```c int32 calculate_sum(int32 N, int32 K, int32 V, int32[] A); ``` * $N$：序列中整数数量; * $K$：指数; * $V$：$x$ 的最大值; * $A$：整数序列; * 在程序开始时，每个测试用例调用本函数的次数最多不超过100次。 这个函数应返回下式的值: $$ \left(\sum_{x=0}^{V} \sum_{l=1}^{N} \sum_{r=l+1}^{N} f_{l,r}(x) \cdot (A[l] + A[r])\right) \bmod 998\,244\,353 $$

无输入。

无输出。

### 示例 #### 示例 1 考虑如下调用： ```c calculate_sum(3, 2, 3, [3, 6, 2]); ``` 应返回 132。 #### 示例 2 考虑如下调用： ```c calculate_sum(7, 1, 0, [1, 2, 3, 4, 5, 6, 7]); ``` 应返回 168。 ### 示例评测器 评测器按照以下格式读取输入： - 第 1 行：三个整数 $N, K, V$ - 第 2 行：$N$ 个整数 $A[1], A[2], \dots, A[N]$ 评测器会调用 `calculate_sum(N, K, V, A)` 并输出返回的值。 # 约束条件 - $1 \le N \le 5 \times 10^5$ - $0 \le K \le 100$ - $0 \le V \le 10^9$ - 对于每个 $i=1 \dots N$，$1 \le A[i] \le 10^9$ # 评分 1. 子任务 1（4 分）：$N=1, K=1$ 2. 子任务 2（8 分）：$N \le 100, K \le 2, V \le 100$ 3. 子任务 3（15 分）：$N \le 100, K \le 100, V \le 100$ 4. 子任务 4（11 分）：$N \le 10^5, K=0$ 5. 子任务 5（17 分）：$N \le 10^5, V=0$ 6. 子任务 6（21 分）：$N \le 10^5, K \le 2$ 7. 子任务 7（11 分）：$N \le 10^5$ 8. 子任务 8（13 分）：无额外限制。 由 ChatGPT 5 翻译