HUST Past Monthly Hard Problems Challenge Contest (1)

From: 2011-05-13 12:00:00 To: 2011-05-13 17:00:00 Now: 2017-09-20 01:09:36 Status: Public

D - RP calculator

Time Limit: 10s Memory Limit: 128MB

Submissions: 434 Solved: 80
Description
As a acmer, RP is important, isn't it? Now this is a RP calculator(see the figure below). There are two rings, each ring has n grids. We call the two grids who have the same degree friendly grids(in figure 1, it's (a0, b0), (a1, b1), ... ,(a7, b7)). When n people come to test their RP, it will work as follows. First, it will generate 2n (a1...an, b1...bn) random integers. For the first people, it first calculator the product of every pair of numbers in the friendly grids, and the RP is the sum of all the products(see figure 1). For the next people, first the outside ring will be rotated 2*PI/n degrees anticlockwise. Then it will work the same as the first people(see figure 2). It will work until n people's RP are all calculated.
Input
The first line of the input file contains an integer T, which show the number of the cases. Then T test cases follows. The first line of every test case contains an integer n(1 <= n <= 50000). The second line contains n numbers a0, a1, ... , an-1.(|ai| < 100). The third line contains n numbers b0, b1, ... , bn-1.(|bi| < 100).
Output
For each test case, print a line containing the n people's RP, separated by a single space.
Sample Input
1

4

4 3 2 1

1 2 3 4
Sample Output
20 26 28 26
Hint
Source
Chen jq