FFT

Теория 1

В следующих местах можно почитать полезные статьи про базовые FFT/NTT:

A: Умножение 1

Даны посл-ти целых чисел $a_0, a_1, \ldots, a_{n - 1}$ и $b_0, b_1, \ldots, b_{m - 1}$. Вычислите посл-ть $c_0, c_1, ..., c_{n + m - 2}$ по правилу:

$$c_k = \sum\limits_{i=0}^k{a_ib_{k-i}}\!\!\!\!\pmod P$$

Здесь полагаем $a_{\geqslant n} = b_{\geqslant m} = 0$. Ограничения: $0 \leqslant a_i, b_i < P$ для $1 \leqslant n, m \leqslant 10^5$ и $P = 998244353$.

4 5
1 2 3 4
5 6 7 8 9

5 16 34 60 70 70 59 36

IDE

B: Умножение 2

Решите предыдущую задачу в ограничениях $1 \leqslant n, m \leqslant 10^6$.

4 5
1 2 3 4
5 6 7 8 9

5 16 34 60 70 70 59 36

★★★

Напишите решение, работающее меньше $1$ сек.

IDE

C: Армия клонов

В точке $(0, 0)$ плоскости Оби-Ван Кеноби создаёт армию из $n\times m$ клонов. Изначально все они целиком ($+1$) принадлежат светлой стороне силы. Далее Оби-Ван запускает каждого клона на какое-то (от $0$ до $n-1$) шагов по вертикали и на какое-то (от $0$ до $m-1$) шагов по горизонтали, причём маршруты всех клонов различны. При движении клон испытывает воздействия силы, меняющие его приверженность вплоть до противоположной (домножающие её на $-1 \leqslant a_i \leqslant 1$ при движении по вертикали и на $-1 \leqslant b_i \leqslant 1$ при движении по горизонтали соответственно).

В каждый момент времени клоны, прибывающие в место назначения через $0 \leqslant k \leqslant n+m-2$ шагов, взаимодействуют друг с другом, кооперируются при приверженности одной стороне силы (светлой или тёмной) и сражаются иначе. Соответственно, их степени приверженности суммируются. Для каждого $k$ выясните итоговое значение получившейся группировки клонов. Числа даны в формате $x.\overline{abcdef}$, ну и $1 \leqslant n, m \leqslant 2\cdot10^5$.

2 2
-0.068697 -0.043599
0.184510 -0.036959

-0.0126753 -0.0055055 0.0016114

IDE

Теория 2

Вот здесь описываются поиск обратного ряда и деление многочленов с точки зрения программирования. Также в данном разделе приведена общая теория про быстрое выполнение разных операции над степенными рядами. А здесь можно прочитать более академическое введение в это.

Смысл там примерно следующий: пусть мы хотим найти $Q(x)$ и $R(x)$, такие что $A(x) = Q(x)B(x) + R(x)$.

Обозначим $\deg(A(x)) = n$ и $\deg(B(x)) = m$. Если $n \geqslant m \geqslant 1$, то выполняется $\deg(Q(x)) = n - m$ и $\deg(R(x)) = t \leqslant m - 1$. Для многочлена $P(x)$ степени $d$ обозначим $P^R(x) = x^d P\!\left(\frac{1}{x}\right)$. Заметим, что это просто многочлен, полученный разворотом коэффициентов $P$.

Раз $A = QB + R$, в частности, $ A\!\left(\frac{1}{x}\right) = Q\!\left(\frac{1}{x}\right)B\!\left(\frac{1}{x}\right) + R\!\left(\frac{1}{x}\right)$, отсюда выводим: $$ x^n A(\tfrac{1}{x}) = x^n Q(\tfrac{1}{x})B(\tfrac{1}{x}) + x^n R(\tfrac{1}{x}) = x^{n-m}Q(\tfrac{1}{x}) \cdot x^m B(\tfrac{1}{x}) + x^{n-t}x^tR(\tfrac{1}{x}) = Q^R(x)B^R(x) + x^{n-m+1}\cdot x^{m-1-t}R^R(x) $$ Таким образом, работая по модулю $x^{n-m+1}$, получаем равенство: $$A^R(x) = Q^R(x)B^R(x), \quad\text{откуда}\quad Q^R(x) = \frac{A^R(x)}{B^R(x)} \!\!\!\pmod{x^{n-m+1}}$$

При этом $\deg(Q^R)$ как раз $n-m$, поэтому другие его коэффициенты (как и коэффициенты $Q$) --- просто $0$.

D: Обратный ряд

Дан многочлен $f(x) = a_{n-1}x^{n-1}+\ldots+a_0$ при $a_0 \neq 0$. Найдите $g(x) = b_{n-1}x^{n-1}+\ldots+b_0$, такой что $f(x)g(x) \equiv 1 \pmod{x^n}$.

В этой задаче $1 \leqslant n, m \leqslant 2\cdot10^5$ и $0 \leqslant a_i, b_i < P$. Здесь и ниже все операции подразумеваются в $\mathbb{Z}_P$ для $P = 998244353$.

3
998244352 998244352 1

998244352 1 998244351

IDE

E: Деление нацело

Даны многочлены $f(x) = a_{n-1}x^{n-1}+\ldots+a_0$, $g(x) = b_{m-1}x^{m-1}+\ldots+b_0$ при $a_{n-1} \neq 0 \neq b_{m-1}$.

Найдите многочлен $Q(x)$, такой что $\deg(f-gQ) < \deg(g)$. Ограничения: $1 \leqslant n, m \leqslant 2\cdot10^5$.

7 3
0 0 0 0 0 0 1
998244352 998244352 1

5 3 2 1 1

IDE

F: Остаток

Решите предыдущую задачу в ограничениях $1 \leqslant n, m \leqslant 5\cdot10^5$ и выведите многочлен $r(x) = f(x)-g(x)Q(x)$.

7 3
0 0 0 0 0 0 1
998244352 998244352 1

5 8

IDE

Теория 3

Быстрое деление многочленов с остатком неразрывно связано с производящими функциями:

G: Линейная рекуррента 1

Пусть дана линейная рекуррентная посл-ть $\{a_0, a_1, \ldots\}$, удовлетворяющая соотношению:

$$a_i = \sum\limits_{j=1}^d{c_ja_{i-j}}, \quad i \geqslant d$$

По известным $a_0, \ldots, a_{d-1}$ и $c_1, \ldots, c_d$ выведите $a_k \!\pmod P$. Здесь $1 \leqslant d \leqslant 10^4$ и $0 \leqslant k \leqslant 10^7$.

2 5
2 3
2 1

IDE

H: Линейная рекуррента 2

Решите предыдущую задачу в ограничениях $1 \leqslant d \leqslant 5\cdot10^4$ и $0\leqslant k \leqslant 10^9$.

2 5
2 3
2 1

★★★

Напишите решение, работающее меньше $2$ сек.

IDE

Теория 4

Каноничная постановка online-FFT следующая: нужно вычислять $C(x) = xA(x)B(x)$, причём очередные коэффициенты $a_k$ и $b_k$ даются только после того, как было вычислено очередное $c_k$. Часто однако подразумевается более распространённая и простая ситуация, когда коэффициенты $A(x)$ известны заранее. Здесь и здесь можно почитать способы обрабатывать такое за $O(n\sqrt{n\log(n)})$ и $O(n\log(n)^2)$ соответственно.

Вкратце идея там следующая: мы расписываем известное $A(x)$ блоками по степеням двойки:

$$A(x) = a_0+\sum\limits_{k=0}^{L-1}{A_k(x)\,x^{2^k}}; \qquad B^k(x) = \sum\limits_{m=0}^{t-1}{B^k_m(x)\,x^{2^k m}} \,\;\text{для}\;\, t = 2^{L-k}$$

После этого $B(x)$ также можно переписать блоками длины по $2^k$, и произведение принимает вид:

$$C(x) = \Big(a_0+\sum\limits_{k=0}^{L-1}{A_k(x)\,x^{2^k}}\Big)B(x) = a_0B(x)+\sum\limits_{k=0}^{L-1}A_k(x)\sum\limits_{m=0}^{t-1}{B^k_m(x)\,x^{2^k(m+1)}}$$

Будем считать каждое из произведений $A_k(x)B^k_m(x)$ отдельно -- его результат прибавляется, начиная с $2^k(m+1)$-го коэффициента, но к этому моменту мы как раз узнаём последний $(2^km+2^k-1)$-ый коэффициент $B^k_m(x)$ и можем честно перемножить его c $A_k(x)$.

I: Online-FFT

Дана посл-ть $(a_n)$. Определим посл-ть $(b_n)$ по следующему правилу: $b_0 = 179$ и

$$b_{n+1} = Collatz\left(\,\sum\limits_{k=0}^n{a_kb_{n-k}} \!\!\!\!\pmod P\right)+1; \qquad Collatz(n) = \Bigg\{\begin{aligned}&n/2, &&n \;\vdots\; 2\\&3n+1, &&\text{иначе}\end{aligned}$$

Для $1 \leqslant n \leqslant 10^5$ по известным $0 \leqslant a_i \leqslant 57$ ($0 \leqslant i < n$) посчитайте значение $b_n$.

2
1 5

IDE

J: безMEXовые перестановки

Как известно, для мн-ва $S \subset\mathbb{Z}_{\geqslant 0}$ его MEX$(S) = \min\{k \in \mathbb{Z}_{\geqslant0}\colon k \notin S\}$. Пусть $a$ --- перестановка чисел $\{0, \ldots, n-1\}$.

Назовём её безMEXовой, если $\forall\,1 \leqslant l < r \leqslant n:$ MEX$(a_l, \ldots, a_r) \neq r-l+1$ (при $r-l \neq n-1$).

По данному $1 \leqslant n \leqslant 2\cdot10^5$ найдите кол-во безMEXовых перестановок длины $n$ по модулю $P = 998244353$.

Хочу решение за O(nlog(n))

На самом деле, эта задача решается и без online-FFT: достаточно выразить производящую функцию через деление многочленов.

IDE