306235: CF1165E. Two Arrays and Sum of Functions

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Two Arrays and Sum of Functions

题意翻译

已知两个长度均为 $n$ 的数组 $a$ 和 $b$。 给定一个函数:$f(l, r) = \sum \limits_{l \le i \le r} a_i \cdot b_i$。 你的任务是对数组 $b$ 中的元素以任意的顺序重新排序,使 $\sum \limits_{1 \le l \le r \le n} f(l, r)$ 的值最小。 由于求和后的答案可能非常大,请将答案模 $998244353$ 之后再输出。请注意,你需要最小化答案而不是其余数。

题目描述

You are given two arrays $ a $ and $ b $ , both of length $ n $ . Let's define a function $ f(l, r) = \sum\limits_{l \le i \le r} a_i \cdot b_i $ . 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.

输入输出格式

输入格式


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

输出格式


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.

输入输出样例

输入样例 #1

5
1 8 7 2 4
9 7 2 9 3

输出样例 #1

646

输入样例 #2

1
1000000
1000000

输出样例 #2

757402647

输入样例 #3

2
1 3
4 2

输出样例 #3

20

Input

题意翻译

已知两个长度均为 $n$ 的数组 $a$ 和 $b$。 给定一个函数:$f(l, r) = \sum \limits_{l \le i \le r} a_i \cdot b_i$。 你的任务是对数组 $b$ 中的元素以任意的顺序重新排序,使 $\sum \limits_{1 \le l \le r \le n} f(l, r)$ 的值最小。 由于求和后的答案可能非常大,请将答案模 $998244353$ 之后再输出。请注意,你需要最小化答案而不是其余数。

加入题单

上一题 下一题 算法标签: