P14035 [PAIO 2025] GCD

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

You are given a sequence of $N$ integers $A[1], A[2], \dots, A[N]$. You are also given an integer $K$ and an integer $V$. Let $\text{gcd}(X_1, X_2, \dots, X_k)$ denote the greatest common divisor of the integers $X_1, X_2, \dots, X_k$. For example, $\text{gcd}(14, 21) = 7$, $\text{gcd}(4, 8, 15) = 1$. We define $f_{l,r}(x) = \text{gcd}(A[1], A[2], \dots, A[l], A[r], \dots, A[N])^K \oplus x$, where $\oplus$ denotes the bitwise XOR operation. Your task is to calculate the sum: $$ \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 $$ ### Implementation Details You need to implement one procedure called `calculate_sum`: ```c int32 calculate_sum(int32 N, int32 K, int32 V, int32[] A); ``` * $N$: the number of integers in the sequence; * $K$: the exponent; * $V$: the maximum value of $x$; * $A$: the sequence of integers; * This procedure might be called no more than 100 times for each test case at the beginning of the program. The procedure should return the sum modulo 998244353: $$ \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 $$

N/A

N/A

### Examples #### Example 1 Consider the following call. ```c calculate_sum(3, 2, 3, [3, 6, 2]); ``` The procedure should return 132. #### Example 2 Consider the following call. ```c calculate_sum(7, 1, 0, [1, 2, 3, 4, 5, 6, 7]); ``` The procedure should return 168. ### Sample Grader The sample grader reads the input in the following format: * Line 1: Three integers $N, K,$ and $V$ * Line 2: $N$ integers $A[1], A[2], \dots, A[N]$ The sample grader calls `calculate_sum(N, K, V, A)` and prints the returned value. ### Constraints * $1 \le N \le 5 \times 10^5$ * $0 \le K \le 100$ * $0 \le V \le 10^9$ * $1 \le A[i] \le 10^9$ for each $i=1 \dots N$. ### Scoring 1. Subtask 1 (4 points): $N=1, K=1$ 2. Subtask 2 (8 points): $N \le 100, K \le 2, V \le 100$ 3. Subtask 3 (15 points): $N \le 100, K \le 100, V \le 100$ 4. Subtask 4 (11 points): $N \le 10^5, K=0$ 5. Subtask 5 (17 points): $N \le 10^5, V=0$ 6. Subtask 6 (21 points): $N \le 10^5, K \le 2$ 7. Subtask 7 (11 points): $N \le 10^5$ 8. Subtask 8 (13 points): No additional constraints.