İkilik
İki ardıcıl həqiqi ədədlər sırasını x(k) və y(k) ilə işarə edək. Kompleks ədədlər ardıcıllığını isə z(k) olaraq təyin edək: z(k) = x(k) + iy(k).
FFT_N(k, z) funksiyasını təyin edək. Eyni qaydada FFT_N(k, x) və FFT_N(k, y) funksiyaları da təyin edilir.
Hesablanmış FFT_N(k, z) dəyərlərindən istifadə edərək FFT_N(k, x) və FFT_N(k, y) dəyərlərini bərpa etmək tələb olunur.
Giriş verilənləri
Giriş faylının ilk sətirində tam ədəd N (1 ≤ N ≤ 2^30, N ikiqatın qüvvətidir) verilir. Daha sonra A, B, C, D, E, F tam qeyri-mənfi ədədləri gəlir ki, bunlar 1000-i keçmir. Vaxt qənaəti üçün FFT_N(k, z) dəyərini aşağıdakı düsturlarla hesablamaq lazımdır:
FFT_N(k, z).real = ((A + B·k) xor (C·k))·10^{-3}, FFT_N(k, z).imag = ((D + E·k) xor (F·k))·10^{-3},
burada FFT_N(k, z).real və FFT_N(k, z).imag — müvafiq olaraq həqiqi və xəyali hissələrdir.
Sonra M — sorğuların sayı (1 ≤ M ≤ 10^5) verilir. Daha sonra M tam ədədləri q_i (0 ≤ q_i ≤ N) gəlir.
Çıxış verilənləri
Çıxış faylına M sətir yazın. j-ci sətirdə FFT_N(q_j, x) və FFT_N(q_j, y) dəyərləri verilməlidir. Dəyərlər düzgün dəyərlərdən 10^{-4}-dən çox fərqlənməməlidir.