Description
Profess X is an expert in signal processing. He has a device which can send a particular 1 second signal repeatedly. The signal is A0 ... An-1 under n Hz sampling.
One day, the device fell on the ground accidentally. Profess X wanted to check whether the device can still work properly. So he ran another n Hz sampling to the fallen device and got B0 ... Bn-1.
To compare two periodic signals, Profess X define the DIFFERENCE of signal A and B as follow:
You may assume that two signals are the same if their DIFFERENCE is small enough. Profess X is too busy to calculate this value. So the calculation is on you. Input
The first line contains a single integer T, indicating the number of test cases.
In each test case, the first line contains an integer n. The second line contains n integers, A0 ... An-1. The third line contains n integers, B0 ... Bn-1.
T≤40 including several small test cases and no more than 4 large test cases.
For small test cases, 0<n≤6⋅103.
For large test cases, 0<n≤6⋅104.
For all test cases, 0≤Ai,Bi<220.
Output
For each test case, print the answer in a single line.
- Sample Input
-
293 0 1 4 1 5 9 2 65 3 5 8 9 7 9 3 251 2 3 4 52 3 4 5 1
Sample Output -
800
/* * hihocoder 1388 Periodic Signal * * 把式子变形一下就是求Ai*Bi+k求和的最大值，想到用FFT来求 * 会因为精度问题不能过，这是找出最小的那个k，然后重新算即可。 */#include
using namespace std;const int MAXN = 200000+10;const double PI = acos(-1.0);struct Complex{ double r,i; Complex(double _r=0,double _i=0):r(_r),i(_i){} Complex operator + (const Complex& rhs) { return Complex(r+rhs.r,i+rhs.i); } Complex operator - (const Complex& rhs) { return Complex(r-rhs.r,i-rhs.i); } Complex operator * (const Complex &rhs) { return Complex(r*rhs.r - i*rhs.i,i*rhs.r + r*rhs.i); }};/* * 进行FFT和IFFT前的反转变换。 * 位置i和 （i二进制反转后位置）互换 * len必须取2的幂 */void Rader(Complex F[],int len){ int j = len >> 1; for(int i = 1;i < len - 1;++i) { if(i < j) swap(F[i],F[j]); // reverse int k = len>>1; while(j>=k) { j -= k; k >>= 1; } if(j < k) j += k; }}/* * 做FFT * len必须为2^k形式， * on==1时是DFT，on==-1时是IDFT */void FFT(Complex F[],int len,int t){ Rader(F,len); for(int h=2;h<=len;h<<=1) { Complex wn(cos(-t*2*PI/h),sin(-t*2*PI/h)); for(int j=0;j