#include #include #include #include #include #include #include #include #include #include #include using namespace std; template class Fast_Fourier_Transform{ // return the vector of F[t] or f[x] where // F[t] = sum of { f[x] * exp(-j * theta * t * x) } in x = 0 .. N-1 (FFT) // f(x) = 1/N * sum of { F[t] * exp(j * theta * t * x) } in t = 0 .. N-1 (inverse FFT) // where theta = 2*PI / N // N == 2^k static vector< complex > do_fft(vector< complex > A, bool inverse){ const T PI = atan2(1, 0) * 2.0; const complex j = complex(0,1); // 0 + j*1.0 (j is the imaginary unit) int N = A.size(); int k = 0; // N = 2^k while(N>>k > 0) k++; for(int bit=0; bit>= 1){ rbit |= tmp_bit & 1; } rbit >>= 1; if(bit < rbit){ swap(A[bit], A[rbit]); } } int dist = 1; T theta = -PI; if(inverse) theta = -theta; for(int level = 1; level W_n = exp(j * theta); complex W(1,0); for(int x=0; x < (1< tmp = A[ y+dist ] * W; A[ y+dist ] = A[ y ] - tmp; A[ y ] += tmp; } W *= W_n; } dist <<= 1; theta *= 0.5; } if(inverse){ T k = 1.0/N; for(int i=0; i static void vec_resize(vector &A, const U val){ int n = A.size(); int k = 1; while(n > k) k<<=1; A.resize(k, val); } public: Fast_Fourier_Transform(){}; static vector< complex > FFT(vector< complex > A){ vec_resize>(A, complex(0,0)); return do_fft(A, false); } static vector< complex > IFFT(vector< complex > A){ //vec_resize>(A, complex(0,0)); return do_fft(A, true); } static vector< complex > FFT(vector A){ vec_resize(A, 0); vector> B(A.size()); for(int i=0; i(A[i], 0); } return do_fft(B, false); } static vector< complex > FFT(vector A){ vec_resize(A, T(0)); vector> B(A.size()); for(int i=0; i(A[i], 0); } return do_fft(B, false); } static vector round(vector> &&A){ vector ret(A.size()); for(int i=0; i C | C[i] = ΣA[i]B[j] static vector> combolution(vector &A, vector &B){ reverse(B.begin(), B.end()); int n = max(A.size(), B.size()); A.resize(n, 0); B.resize(n, 0); auto A_FFT = FFT(A); auto B_FFT = FFT(B); for(int i=0; i> L >> M >> N; vector A(L), B(M); for(int i=0; i> A[i]; } for(int i=0; i> B[i]; } int Q; cin >> Q; int sz = 1; while(N >= sz) sz <<= 1; vector A_(sz*2, 0); for(int i=0; i B_(sz, 0); for(int i=0; i::round(Fast_Fourier_Transform::combolution(A_, B_)); for(int i=0; i