Ряд Фурье

[Allxy]

Описание
Горячий участок одной программы расчета течения жидкости вычисляет сумму ряда

$$\sum_{i=0}^{N}\sum_{j=0}^{N} a_{ij}\cos(ix)\cos(jy)$$

для набора из M точек $(x,y)$, принадлежащих области течения $[-\pi/2;\pi/2]^2$. Запрограммируйте как можно более быстрый алгоритм расчета данной суммы. Коэффициенты $a_i_j$ задайте формулой

$$a_{ij} = \frac {1} {1+i+j+\frac{1}{\sqrt{1+ij}}}.$$

Помогите, люди добрые. Не получается ничего :(

[sanaris]

Метод схлопывания пополам.
Область i,j бьётся на четвертинки, над каждой вызывается рекурсия.
Пока четвертинки не станут достаточно маленькими, чтобы напрямую сложить - 4 или 16 например.

[Vince Diesel]

Не знаю, какое олимпиадное решение подразумевается, но по-нормальному, раз "горячий участок", то много раз считается, и, вероятно, пределы для возможных значений $N$ известны. Так что имеет смысл заранее посчитать значения коэффициентов и хранить в массиве. Сгруппируем слагаемые, вынося $\cos i x$ и получим алгоритм с $N(N+1)$ умножениями и $2N$ вычислениями косинусов. Поскольку вычисление косинусов медленнее, чем умножение, можно вычислять их рекуррентно по формулам приведения. В общем, получится $O(N^2)$ умножений плюс вычисление $\cos x$, $\sin x$, $\cos y$, $\sin y$.

[ihq.pl]

Это же дискретное преобразование Фурье массива $a_{ij}$. Для него написаны быстрые алгоритмы. Например, "Численные методы" Кобельков, Жидков.