Description

给定一个长度为 $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 的函数：

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$$

Input Format

无输入。

Output Format

无输出。

Hint

示例

示例 1

考虑如下调用：

calculate_sum(3, 2, 3, [3, 6, 2]);

应返回 132。

示例 2

考虑如下调用：

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 翻译