Изменения
Нет описания правки
# Даны 2 числа в десятичной системе счисления, каждое состоит из $n$ десятичных цифр. Найдите их произведение за $O(n \log n)$.
# Даны две строки $p$ и $t$ из символов 0 и 1 ($|p| \le |t|$). Найдите расстояние Хэмминга между $p$ и всеми подстроками $t[i..i+|p|-1]$ длины $|p|$ за $O(n \log n)$.
# Задан многочлен $A(x) = \sum\limits_{i=0}^{n - 1} a_i x^i, a_0 \neq 0$. Найдите такой многочлен $B(x)$, что $A(x) \times B(x) \equiv = 1 + x^n Q(x)$ для какого-то многочлена $Q(x)$ за $O(n \log^2 n)$.
# То же самое за $O(n \log n)$.
</wikitex>
