题面

原题链接

大秦为你打开题目传送门

题目翻译

定义某数组 $x$ 的权值为

$$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n(x_i+x_j)^2$$

现在，给定两个长度为 $n$ 的数组 $a,b$。你可以执行若干次操作，每次操作选择一个下标 $i$，并交换 $a_i,b_i$。求在进行操作之后两个数组的权值之和最小能够达到多少。

数据范围：

$t$ 组数据，$1\leqslant t\leqslant 40$。
$1\leqslant n,\sum n\leqslant 100$。
$1\leqslant a_i,b_i\leqslant 100$。

Translated by Eason_AC

输入格式

Each test case consists of several test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 40 $ ) — the number of test cases. The following is a description of the input data sets.

The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 100 $ ) — the length of both arrays.

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 100 $ ) — elements of the first array.

The third line of each test case contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \leq b_i \leq 100 $ ) — elements of the second array.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 100 $ .

输出格式

For each test case, print the minimum possible total cost.

思路

首先，考虑把题目给出的式子展开来。

首先完全平方公式把 $(x_i + x_j)^2$ 拆成 ${x_i}^2+{x_j}^2 + 2x_ix_j$ 。方便后面的推导我们把平方项都放在前面。

然后我们可以来数一数每一个数出现的次数。当 $n = 3$ 的时候匹配如下：

1
2
3

1 2 
1 3 
2 3

发现所有数字都出现了 $2$ 次。难道是巧合？再来，$n = 4$ 。

我们发现每一个数字都会被选上 $n -1$ 次。得到原式子展开后的中的第一个部分：
$$
(n-1)\sum\limits_{i = 1}^{n}({a_i}^2 + {b_i}^2)
$$
接下来考虑下一个部分，也就是剩下的 $2x_ix_j$ 怎么处理。我们把这个拆开写写成 $x_i x_j + x_jx_i$ 的形式，为什么要这样变呢？我们多来几项试试。
$$
2ab + 2ac + 2ad + 2bc + 2bd + 2cd = ab + ba + ac + ca + ad + da + bc + cb + bd + db + cd + dc
$$
把每一个字母单独提出来：
$$
a(b + c + d) + b(a + c + d) + c(a + b + d) + d(a + b + c)
$$
每一个都是形如 $x_i[ (\sum\limits_{j = 1}^{n} x_j) - x_i]$ 形式的式子，我们把这个序列的和设为 $S$ 。可得：
$$
x_i (S - x_i) = x_i\ \dot{}\ S - {x_i}^2
$$
我们发现又是 ${x_i}^2$ 可以套上面的公式，但是属于是又重新抽了一个出来，也就是说系数还得改成 $n - 2$ 。

最后，我么们得到的式子就是：
$$
\sum\limits_{i}^{\infty} \cfrac{1}{2^i} \times i
$$