[SOLUTION] Summing the values SOLUTION CODECHEF

Problem SOLUTION CODECHEF

For an array $B$ of length $M$, we define its value $f(B)$ as follows:

In particular, if $M=1$ then $f(B)=0$.

You’re given an array $A$ of length $N$.
Find the sum of values of all of its subarrays.
That is, compute

where $A[L\dots R]$ denotes the subarray [��,��+1,��+2,…,��][AL​,AL+1​,AL+2​,…,AR​].

The answer can be large, so print it modulo $998244353$.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of two lines of input.
  • The first line of each test case contains a single integer $N$ — the size of the array.
  • The next line contains $N$ space-separated integers �1,�2,…,��A1​,A2​,…,AN​.

Output Format

For each test case, output on a new line the sum of values of all subarrays of the array, modulo $998244353$.

Constraints

Sample 1:

3
1
1
3
3 2 1
3
1 2 3

0
6
998244347

Explanation:

For the first testcase, we can have only size 1 subarray and hence answer comes out to be 0.

In the second testcase, we can find the final sum and that comes out to be 6.

In the third testcase, our sum comes negative and hence the value after applying modulo operator becomes 998244347

SOLUTION

# Function to calculate the sum of values of all subarrays modulo 998244353
def sum_of_subarrays(arr):
mod = 998244353
n = len(arr)
result = 0
prefix_sum = 0
suffix_sum = 0

for i in range(n):
prefix_sum = (prefix_sum + arr[i]) % mod
suffix_sum = (suffix_sum + (i + 1) * arr[i]) % mod
result = (result + (i + 1) * prefix_sum – suffix_sum) % mod

return result

# Number of test cases
T = int(input())

# Iterate through each test case
for _ in range(T):
N = int(input())
A = list(map(int, input().split()))

# Call the function to calculate the sum of values of all subarrays
result = sum_of_subarrays(A)

# Output the result modulo 998244353
print(result % 998244353)