题目背景

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+1], \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}^{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:

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}^{N} f_{l,r}(x) \cdot (A[l] + A[r])\right) \bmod 998\,244\,353 $$

提示

Examples

Example 1

Consider the following call.

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

The procedure should return 132.

Example 2

Consider the following call.

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.