# Докажите, что двойственный к матричному матроид является матричным. Как устроена его матрица?
# Когда двойственный к графовому матроид является графовым?
# Задан многочлен $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)$.
# Докажите, что $DFT(DFT(\langle a_0, a_1, \ldots, a_{n-1} \rangle)) = n \cdot \langle a_0, a_{n-1}, a_{n-2}, \ldots, a_1 \rangle$
# Опишите модификацию алгоритма 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)$.
# Даны две строки $p$ и $t$ из символов 0 и 1 ($|p| \le |t|$). Найдите расстояние Хэмминга между $p$ и всеми подстроками $t[i..i+|p|-1]$ длины $|p|$ за $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)$ .# Каков критерий существования решения и алгоритм восстановления числа в КТО, если убрать требование взаимной простоты модулей $m_1$ и $m_2$?# Чему равна сумма всех чисел от 0 до $n-1$, взаимнопростых с $n$?# Найдите $\frac{n!}{p^k} \mod p$, где $k$ - максимальная степень вхождения простого $p$ в $n!$, за $O(p \log n)$# Докажите, что $gcd$ последовательных чисел Фибоначчи равен 1.# Докажите, что $gcd(F_n, F_m) = F_{gcd(n, m)}$.# Для заданных $a$ и нечетного простого $p$, проверьте, что существует $x$: $x^2 \equiv a \mod p$ за $O(\log p)$# Решите задачу дискретного логарифма для простого модуля $p$ вида $2^k + 1$ за $O(\mathop{poly}(k))$.# Докажите лемму о паросочетании в графе замен (формулировка тут: [very hardhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B8_%D0%B2_%D0%B3%D1%80%D0%B0%D1%84%D0%B5_%D0%B7%D0%B0%D0%BC%D0%B5%D0%BD], доказательство неправильное - неверный индукционный переход)# Рассмотрим два матроида $M_1$ и $M_2$. Как связаны максимальное независимое множество пересечения $M_1 \cap M_2$ и база $M_1 \cup M_2^*$? ($M_2^*$ - матроид, двойственный $M_2$)# Докажите теорему Радо: пусть $M$ - матроид с ранговой функцией $r$, $X = X_1 \cup X_2 \cup ...\cup X_k$, причем все $X_i$ попарно не пересекаются. Будем называть независимой системой представителей независимое множество $A$, такое что $|A \cap X_i| \le 1$. Пусть $A_{max}$ - максимальная по мощности независимая система представителей. Тогда $|A_{max}|=\min_{Z\subset \{1,..,k\}}(r(\cup_{i\in Z} X_i)+k-|Z|)$.# Предложите алгоритм построения максимальной независимой системы представителей.# Докажите, что длина кратчайшего пути из $S$ в $T$ в алгоритме построения базы пересечения матроидов не убывает.# Докажите, что число различных длин кратчайшего пути из $S$ в $T$, которые встречаются в алгоритме построения базы пересечения матроидов, есть $O(\sqrt n)$.# Докажите, что сумма длин кратчайших пути из $S$ в $T$, которые встречаются в алгоритме построения базы пересечения матроидов, есть $O(n \log n)$.# Игра Шеннона. Рассмотрим игру на связном графе с множеством ребер $E$. Играют два игрока, cut и link, первым ходит cut. Игроки по очереди добавляют себе ребра, не использованные на предыдущих ходах. В конце игры link выигрывает, если по его ребрам можно дойти от любой вершины до любой. Докажите, что link выигрывает при оптимальной игре, если и только если в графе существует два непересекающихся остовных дерева.# Игра Шеннона на произвольном матроиде. Рассмотрим игру на матроиде $M$. Играют два игрока, cut и link, первым ходит cut. Игроки по очереди выбирают себе элементы носителя, не использованные на предыдущих ходах. В конце игры link выигрывает, если его множество содержит базу матроида. Докажите, что link выигрывает при оптимальной игре, если и только если в графе существует две непересекающихся базы.# Пусть $M$ - невырожденная квадратная матрица над вещественными числами. Докажите, что для любого множества строк $R$ найдется множество столбцов той же мощности $C$, что миноры $R\times C$ и $\overline{R}\times \overline{C}$ - ненулевые (как $\overline T$ обозначено множество строк/столбцов, не входящих в $T$).# Задан двудольный граф, каждая вершина имеет вес. Требуется выбрать паросочетание, чтобы суммарный вес покрытых вершин был максимален. Решите эту задачу, не используя сведение к обычной задаче о назначениях.
</wikitex>
