eolymp
bolt
Try our new interface for solving problems
Məsələlər

Раздвоение

Раздвоение

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Обозначим две последовательности действительных чисел x(k) и y(k). Определим последовательность комплексных чисел z(k): z(k) = x(k) + iy(k).

Пусть FFT_N(k, z) = . Аналогичным образом определяются FFT_N(k, x) и FFT_N(k, y).

Требуется по вычисленным значениям FFT_N(k, z) восстановить значения FFT_N(k, x) и FFT_N(k, y).

Giriş verilənləri

В первой строке входного файла записано целое число N (1N2^30, N является степенью двойки). Далее следуют целые неотрицательные числа A, B, C, D, E, F, не превосходящие 1000. Для экономии времени ввода значения FFT_N(k, z) нужно будет вычислять по следующим формулам:

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},

где FFT_N(k, z).real и FFT_N(k, z).imag — действительная и мнимая части соответственно.

Затем дано число M — количество запросов (1M10^5). Далее следуют M целых чисел q_i (0q_iN).

Çıxış verilənləri

В выходной файл выведите M строк. В j-ой строке — значения FFT_N(q_j, x) и FFT_N(g_j, y). Значения должны отличаться от правильных не более, чем на 10^{-4}.

Nümunə

Giriş verilənləri #1
2
1000 0 0 0 0 0
2
0 1
Çıxış verilənləri #1
1.0000 0.0000 0.0000 0.0000
1.0000 0.0000 0.0000 0.0000
Müəllif Дмитрий Жуков
Mənbə Зимняя Школа, Харьков 2011, День 2