1165E.md (1476B)
1 Source: https://codeforces.com/problemset/problem/1165/E 2 3 E. Two Arrays and Sum of Functions 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two arrays $a$ and $b$, both of length $n$. 22 23 Let's define a function $f(l, r) = \sum\limits_{l \le i \le r} a_i \cdot b_i$. 24 25 Your task is to reorder the elements (choose an arbitrary order of elements) of the array $b$ to minimize the value of $\sum\limits_{1 \le l \le r \le n} f(l, r)$. Since the answer can be very large, you have to print it modulo $998244353$. Note that you should minimize the answer but not its remainder. 26 27 Input 28 29 The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$ and $b$. 30 31 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), where $a_i$ is the $i$-th element of $a$. 32 33 The third line of the input contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_j \le 10^6$), where $b_j$ is the $j$-th element of $b$. 34 35 Output 36 37 Print one integer — the minimum possible value of $\sum\limits_{1 \le l \le r \le n} f(l, r)$ after rearranging elements of $b$, taken modulo $998244353$. Note that you should minimize the answer but not its remainder. 38 39 Examples 40 41 Input 42 43 ``` 44 5 45 1 8 7 2 4 46 9 7 2 9 3 47 ``` 48 49 Output 50 51 ``` 52 646 53 ``` 54 55 Input 56 57 ``` 58 1 59 1000000 60 1000000 61 ``` 62 63 Output 64 65 ``` 66 757402647 67 ``` 68 69 Input 70 71 ``` 72 2 73 1 3 74 4 2 75 ``` 76 77 Output 78 79 ``` 80 20 81 ```