Изменения

# Задан многочлен $A(x) = \sum\limits_{i=0}^n a_i x^i$ степени $n$ и точка число $x_0$. Найдите представление $A(x)$ в виде $A(x) = q(x) \cdot (x - x_0) + r$, где $r$~--- число, а $q(x) $~--- многочлен степени $n-1$ за время $O(n)$.# Предложите способ восстановления коэффициентов многочлена $A(x) = \sum\limits_{i=0}^{n-1} a_i x^i$ по заданным $n+1$ парам $\{(x_0, y_0), (x_1, y_1), \ldots (x_{n-1}x_n, y_{n-1}y_n)\}$, где $y_i = A(x_i)$ и все $x_i$ различны, за $O(n^2)$.# Пусть заданы значения многочлена $A(x)$ степени $n$ для всех $x = 0, 1, \ldots, n$. Для заданного числа $t > n$ посчитайте $A(t)$ за $O(n)$.

# Опишите модификацию алгоритма FFT для случая, когда размер массива является степенью 3 тройки ($n = 3^k$). Какое будет рекуррентное соотношение для времени работы и само время работы в таком случае? Указание: как разделить на 3 многочлена и как скомпоновать результаты?# Как за один вызов алгоритма FFT посчитать преобразование Фурье 2 многочленов $A$ и $B$ с вещественными коэффициентами? Указание: нужно объединить 2 многочлена степени $n$ в один многочлен $C$ степени $n$ с комплексными коэффициентами и восстановить $DFT(A)$ и $DFT(B)$ по $DFT(C)$.# Для заданных $n$ различных чисел $x_0, x_1, \ldots, x_{n-1}$ постройте многочлен $n$ -й степени, который имеет корни только в заданных $n$ точках за $O(n \log^2 n)$# Пусть мы хотим считать преобразование Фурье не в поле комплексных чисел, а в поле остатков по модулю $p$, где $p$~--- простое число. Для каких $p$ такое преобразование можно сделать, как найти соответствующий корень $n$-й степени из единицы $\omega_n$, и как изменится сам алгоритм?# Даны 2 числа в десятичной системе счисления, каждое состоит из $n$ десятичных цифр. Найдите их произведение за $O(n \log n)$.

# Для всех чисел $n$ от 1 до $N$ посчитайте количество представлений вида $n = a\cdot b + c \cdot d$, $a, b, c, d > 0$ за $O(n \log n)$.# Задан многочлен $A(x) = \sum\limits_{i=0}^{2^kn -1} a_i x^i, a_0 \neq 0$. Найдите такой многочлен $B(x)$, что $A(x) \times B(x) \equiv 1 \bmod + x^n Q(x)$ для какого-то многочлена $Q(x^{2^k})$ за $O(n \log^2 n)$ [hard].# То же самое за $O(n \log n)$ [very hard].