merge

10 files changed, 199 insertions, 162 deletions

diff --git a/math/binomial0.cpp b/math/binomial0.cpp
index d9af917..896a0f1 100644
--- a/math/binomial0.cpp
+++ b/math/binomial0.cpp
@@ -10,5 +10,5 @@ void precalc() {
 
 ll calc_binom(ll n, ll k) {
 	if (n < 0 || n < k || k < 0) return 0;
-	return (fac[n] * fac[n-k] % mod) * fac[k] % mod;
+	return (inv[n] * inv[n-k] % mod) * fac[k] % mod;
 }
diff --git a/math/binomial1.cpp b/math/binomial1.cpp
index 02b27e3..dab20b3 100644
--- a/math/binomial1.cpp
+++ b/math/binomial1.cpp
@@ -2,8 +2,7 @@ ll calc_binom(ll n, ll k) {
 	if (k > n) return 0;
 	ll r = 1;
 	for (ll d = 1; d <= k; d++) {// Reihenfolge => Teilbarkeit
-		r *= n--;
-		r /= d;
+		r *= n--, r /= d;
 	}
 	return r;
 }
diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp
index 623f94b..ccbc5dc 100644
--- a/math/chineseRemainder.cpp
+++ b/math/chineseRemainder.cpp
@@ -1,35 +1,14 @@
-// Laufzeit: O(n * log(n)), n := Anzahl der Kongruenzen. Nur für
-// teilerfremde Moduli. Berechnet das kleinste, nicht negative x,
-// das alle Kongruenzen simultan löst. Alle Lösungen sind
-// kongruent zum kgV der Moduli (Produkt, da teilerfremd).
-struct ChineseRemainder {
+struct CRT {
 	using lll = __int128;
-	vector<lll> lhs, rhs, mods, inv;
-	lll M; // Produkt über die Moduli. Kann leicht überlaufen.
+	lll M = 1, sol = 0; // Solution unique modulo M
+	bool hasSol = true;
 
-	ll g(const vector<lll> &vec) {
-		lll res = 0;
-		for (int i = 0; i < sz(vec); i++) {
-			res += (vec[i] * inv[i]) % M;
-			res %= M;
-		}
-		return res;
-	}
-
-	// Fügt Kongruenz l * x = r (mod m) hinzu.
-	void addEquation(ll l, ll r, ll m) {
-		lhs.push_back(l);
-		rhs.push_back(r);
-		mods.push_back(m);
-	}
-
-	ll solve() { // Löst das System.
-		M = accumulate(all(mods), lll(1), multiplies<lll>());
-		inv.resize(sz(lhs));
-		for (int i = 0; i < sz(lhs); i++) {
-			lll x = (M / mods[i]) % mods[i];
-			inv[i] = (multInv(x, mods[i]) * (M / mods[i]));
-		}
-		return (multInv(g(lhs), M) * g(rhs)) % M;
+	// Adds congruence x = a (mod m)
+	void add(ll a, ll m) {
+		auto [d, s, t] = extendedEuclid(M, m);
+		if((a - sol) % d != 0) hasSol = false;
+		lll z = M/d * s;
+		M *= m/d;
+		sol = (z % M * (a-sol) % M + sol + M) % M;
 	}
 };
diff --git a/math/extendedEuclid.cpp b/math/extendedEuclid.cpp
index d016a63..ecf4a16 100644
--- a/math/extendedEuclid.cpp
+++ b/math/extendedEuclid.cpp
@@ -1,7 +1,6 @@
 // a*x + b*y = ggt(a, b)
-ll extendedEuclid(ll a, ll b, ll& x, ll& y) {
-	if (a == 0) {x = 0; y = 1; return b;}
-	ll x1, y1, d = extendedEuclid(b % a, a, x1, y1);
-	x = y1 - (b / a) * x1; y = x1;
-	return d;
+array<ll, 3> extendedEuclid(ll a, ll b) {
+	if (a == 0) return {b, 0, 1};
+	auto [d, x, y] = extendedEuclid(b % a, a);
+	return {d, y - (b / a) * x, x};
 }
diff --git a/math/math.tex b/math/math.tex
index 8ccc55e..f9a5ea5 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -1,5 +1,12 @@
 \section{Mathe}

 

+\begin{algorithm}{Zykel Erkennung}

+	\begin{methods}

+		\method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l}

+	\end{methods}

+	\sourcecode{math/cycleDetection.cpp}

+\end{algorithm}

+

 \begin{algorithm}{Longest Increasing Subsequence}

 	\begin{itemize}

 		\item \code{lower\_bound} $\Rightarrow$ streng monoton

@@ -7,14 +14,6 @@
 	\end{itemize}

 	\sourcecode{math/longestIncreasingSubsequence.cpp}

 \end{algorithm}

-\columnbreak

-

-\begin{algorithm}{Zykel Erkennung}

-	\begin{methods}

-		\method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l}

-	\end{methods}

-	\sourcecode{math/cycleDetection.cpp}

-\end{algorithm}

 

 \begin{algorithm}{Permutationen}

 	\begin{methods}

@@ -44,21 +43,20 @@
 

 \begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus}

 	\runtime{\log(a) + \log(b)}

-	\sourcecode{math/gcd-lcm.cpp}

 	\sourcecode{math/extendedEuclid.cpp}

 \end{algorithm}

 

-\subsection{Multiplikatives Inverses von $\boldsymbol{n}$ in $\boldsymbol{\mathbb{Z}/p\mathbb{Z}}$}

-\textbf{Falls $\boldsymbol{p}$ prim:}\quad $x^{-1} \equiv x^{p-2} \bmod p$

+\subsection{Multiplikatives Inverses von $\boldsymbol{x}$ in $\boldsymbol{\mathbb{Z}/m\mathbb{Z}}$}

+\textbf{Falls $\boldsymbol{m}$ prim:}\quad $x^{-1} \equiv x^{m-2} \bmod m$

 

-\textbf{Falls $\boldsymbol{\ggT(n, p) = 1}$:}

+\textbf{Falls $\boldsymbol{\ggT(x, m) = 1}$:}

 \begin{itemize}

 	\item Erweiterter euklidischer Algorithmus liefert $\alpha$ und $\beta$ mit

-	$\alpha n + \beta p = 1$.

-	\item Nach Kongruenz gilt $\alpha n + \beta p \equiv \alpha n \equiv 1 \bmod p$.

-	\item $n^{-1} :\equiv \alpha \bmod p$

+	$\alpha x + \beta m = 1$.

+	\item Nach Kongruenz gilt $\alpha x + \beta m \equiv \alpha x \equiv 1 \bmod m$.

+	\item $x^{-1} :\equiv \alpha \bmod m$

 \end{itemize}

-\textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$.

+\textbf{Sonst $\boldsymbol{\ggT(x, m) > 1}$:}\quad Es existiert kein $x^{-1}$.

 % \sourcecode{math/multInv.cpp}

 \sourcecode{math/shortModInv.cpp}

 

@@ -121,19 +119,12 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/divisors.cpp}

 \end{algorithm}

 

-\begin{algorithm}{Primitivwurzeln}

-	\begin{itemize}

-		\item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$

-		\item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln

-		\item Sei $g$ Primitivwurzel modulo $n$.

-		Dann gilt:\newline

-		Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$.

-	\end{itemize}

-	\begin{methods}

-		\method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)}

-		\method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)}

-	\end{methods}

-	\sourcecode{math/primitiveRoot.cpp}

+\begin{algorithm}{Numerisch Extremstelle bestimmen}

+	\sourcecode{math/goldenSectionSearch.cpp}

+\end{algorithm}

+

+\begin{algorithm}{Numerisch Integrieren, Simpsonregel}

+	\sourcecode{math/simpson.cpp}

 \end{algorithm}

 

 \begin{algorithm}{Diskreter Logarithmus}

@@ -151,6 +142,22 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/discreteNthRoot.cpp}

 \end{algorithm}

 

+

+\begin{algorithm}{Primitivwurzeln}

+	\begin{itemize}

+		\item Primitivwurzel modulo $n$ existiert $\Leftrightarrow$ $n \in \{2,\ 4,\ p^\alpha,\ 2\cdot p^\alpha \mid\ 2 < p \in \mathbb{P},\ \alpha \in \mathbb{N}\}$

+		\item es existiert entweder keine oder $\varphi(\varphi(n))$ inkongruente Primitivwurzeln

+		\item Sei $g$ Primitivwurzel modulo $n$.

+		Dann gilt:\newline

+		Das kleinste $k$, sodass $g^k \equiv 1 \bmod n$, ist $k = \varphi(n)$.

+	\end{itemize}

+	\begin{methods}

+		\method{isPrimitive}{prüft ob $g$ eine Primitivwurzel ist}{\log(\varphi(n))\*\log(n)}

+		\method{findPrimitive}{findet Primitivwurzel (oder -1)}{\abs{ans}\*\log(\varphi(n))\*\log(n)}

+	\end{methods}

+	\sourcecode{math/primitiveRoot.cpp}

+\end{algorithm}

+

 \begin{algorithm}{Linearessieb und Multiplikative Funktionen}

 	Eine (zahlentheoretische) Funktion $f$ heißt multiplikativ wenn $f(1)=1$ und $f(a\cdot b)=f(a)\cdot f(b)$, falls $\ggT(a,b)=1$.

 	

@@ -185,7 +192,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\end{itemize}

 \end{algorithm}

 

-

 \begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}}

 	\begin{itemize}

 		\item Bis $10^8$ in unter 64MB Speicher (lange Berechnung)

@@ -216,33 +222,25 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	%\sourcecode{math/mobius.cpp}

 \end{algorithm}

 

-%\columnbreak

-%\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}

-%\begin{itemize}

-%	\item Zählt die relativ primen Zahlen $\leq n$.

-%	

-%	\item Multiplikativ:

-%	$\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$

-%	

-%	\item $p$ prim, $k \in \mathbb{N}$:

-%	$~\varphi(p^k) = p^k - p^{k - 1}$

-%	

-%	\item \textbf{\textsc{Euler}'s Theorem:}

-%	Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.

-%	Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:

-%	$a^{m} \equiv a \pmod{m}$

-%\end{itemize}

-%\sourcecode{math/phi.cpp}

-

-

-\begin{algorithm}{Numerisch Extremstelle bestimmen}

-	\sourcecode{math/goldenSectionSearch.cpp}

-\end{algorithm}

-

-

-\begin{algorithm}{Numerisch Integrieren, Simpsonregel}

-	\sourcecode{math/simpson.cpp}

-\end{algorithm}

+\optional{

+\columnbreak

+\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion}

+\begin{itemize}

+	\item Zählt die relativ primen Zahlen $\leq n$.

+	

+	\item Multiplikativ:

+	$\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$

+	

+	\item $p$ prim, $k \in \mathbb{N}$:

+	$~\varphi(p^k) = p^k - p^{k - 1}$

+	

+	\item \textbf{\textsc{Euler}'s Theorem:}

+	Für $b \geq \varphi(c)$ gilt: $a^b \equiv a^{b \bmod \varphi(c) + \varphi(c)} \pmod{c}$. Darüber hinaus gilt: $\gcd(a, c) = 1 \Leftrightarrow a^b \equiv a^{b \bmod \varphi(c)} \pmod{c}$.

+	Falls $m$ prim ist, liefert das den \textbf{kleinen Satz von \textsc{Fermat}}:

+	$a^{m} \equiv a \pmod{m}$

+\end{itemize}

+\sourcecode{math/phi.cpp}

+}

 

 \begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}

 	Multipliziert Polynome $A$ und $B$.

@@ -259,21 +257,53 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	%\textcolor{safeOrange}{$\blacksquare$} NTT code, %\textcolor{safeGreen}{$\blacksquare$} FFT code

 	\sourcecode{math/transforms/fft.cpp}

 	\sourcecode{math/transforms/ntt.cpp}

+    \vfill*

+    \columnbreak

 	\sourcecode{math/transforms/bitwiseTransforms.cpp}

 	Multiplikation mit 2 transforms statt 3: (nur benutzten wenn nötig!)

 	\sourcecode{math/transforms/fftMul.cpp}

 \end{algorithm}

 

-\subsection{LGS über $\boldsymbol{\mathbb{R}}$}

-\method{gauss}{löst LGS}{n^3}

-\sourcecode{math/gauss.cpp}

+\begin{algorithm}{Operations on Formal Power Series}

+    \sourcecode{math/transforms/seriesOperations.cpp}

+\end{algorithm}

 

 \subsection{LGS über $\boldsymbol{\mathbb{F}_p}$}

 \method{gauss}{löst LGS}{n^3}

 \sourcecode{math/lgsFp.cpp}

 

-\clearpage

+\subsection{LGS über $\boldsymbol{\mathbb{R}}$}

+\method{gauss}{löst LGS}{n^3}

+\sourcecode{math/gauss.cpp}

+

+\begin{algorithm}{\textsc{Legendre}-Symbol}

+	Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:

+	\begin{align*}

+		\legendre{a}{p} &=

+		\begin{cases*}

+		\hphantom{-}0 & falls $p~\vert~a$ \\[-1ex]

+		\hphantom{-}1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \bmod p$ \\[-1ex]

+		-1 & sonst

+		\end{cases*} \\

+		\legendre{-1}{p} = (-1)^{\frac{p - 1}{2}} &=

+		\begin{cases*}

+		\hphantom{-}1 & falls $p \equiv 1 \bmod 4$ \\[-1ex]

+		-1 & falls $p \equiv 3 \bmod 4$

+		\end{cases*} \\

+		\legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}} &=

+		\begin{cases*}

+		\hphantom{-}1 & falls $p \equiv \pm 1 \bmod 8$ \\[-1ex]

+		-1 & falls $p \equiv \pm 3 \bmod 8$

+		\end{cases*}

+	\end{align*}

+	\begin{align*}

+		\legendre{p}{q} \cdot \legendre{q}{p} = (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} &&

+		\legendre{a}{p} \equiv a^{\frac{p-1}{2}}\bmod p

+	\end{align*}

+	\sourcecode{math/legendre.cpp}

+\end{algorithm}

 

+\optional{

 \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}

 \begin{methods}

 	\method{init}{berechnet $\pi$ bis $N$}{N\*\log(\log(N))}

@@ -281,6 +311,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\method{pi}{zählt Primzahlen  $\leq n$ ($n < N^2$)}{n^{2/3}}

 \end{methods}

 \sourcecode{math/piLehmer.cpp}

+}

 

 \begin{algorithm}{Lineare-Recurenz}

 	\begin{methods}

@@ -331,33 +362,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\sourcecode{math/matrixPower.cpp}

 \end{algorithm}

 

-\begin{algorithm}{\textsc{Legendre}-Symbol}

-	Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$:

-	\begin{align*}

-		\legendre{a}{p} &=

-		\begin{cases*}

-		\hphantom{-}0 & falls $p~\vert~a$ \\[-1ex]

-		\hphantom{-}1 & falls $\exists x \in \mathbb{Z}\backslash p\mathbb{Z} : a \equiv x^2 \bmod p$ \\[-1ex]

-		-1 & sonst

-		\end{cases*} \\

-		\legendre{-1}{p} = (-1)^{\frac{p - 1}{2}} &=

-		\begin{cases*}

-		\hphantom{-}1 & falls $p \equiv 1 \bmod 4$ \\[-1ex]

-		-1 & falls $p \equiv 3 \bmod 4$

-		\end{cases*} \\

-		\legendre{2}{p} = (-1)^{\frac{p^2 - 1}{8}} &=

-		\begin{cases*}

-		\hphantom{-}1 & falls $p \equiv \pm 1 \bmod 8$ \\[-1ex]

-		-1 & falls $p \equiv \pm 3 \bmod 8$

-		\end{cases*}

-	\end{align*}

-	\begin{align*}

-		\legendre{p}{q} \cdot \legendre{q}{p} = (-1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} &&

-		\legendre{a}{p} \equiv a^{\frac{p-1}{2}}\bmod p

-	\end{align*}

-	\sourcecode{math/legendre.cpp}

-\end{algorithm}

-

 \begin{algorithm}{Inversionszahl}

 	\sourcecode{math/inversions.cpp}

 \end{algorithm}

@@ -405,20 +409,20 @@ so gilt
 %\begin{algorithm}{Binomialkoeffizienten}

 \paragraph{Binomialkoeffizienten}

 	Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.

+	

 	\begin{methods}

 		\method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}}

 		\method{calc\_binom}{berechnet Binomialkoeffizient}{1}

 	\end{methods}

 	\sourcecode{math/binomial0.cpp}

 	Falls $n >= p$ for $\mathit{mod}=p^k$ berechne \textit{fac} und \textit{inv} aber teile $p$ aus $i$ und berechne die häufigkeit von $p$ in $n!$ als $\sum\limits_{i=1}\big\lfloor\frac{n}{p^i}\big\rfloor$

-\columnbreak

-	

-	\begin{methods}

+

+    \begin{methods}

 		\method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}

 	\end{methods}

 	\sourcecode{math/binomial1.cpp}

-	

-	\begin{methods}

+

+    \begin{methods}

 		\method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}

 	\end{methods}

 	\sourcecode{math/binomial3.cpp}

diff --git a/math/multInv.cpp b/math/multInv.cpp
index 87603f3..647dc2d 100644
--- a/math/multInv.cpp
+++ b/math/multInv.cpp
@@ -1,5 +1,4 @@
-ll multInv(ll n, ll p) {
-	ll x, y;
-	extendedEuclid(n, p, x, y); // Implementierung von oben.
-	return ((x % p) + p) % p;
+ll multInv(ll x, ll m) {
+	auto [d, a, b] = extendedEuclid(x, m); // Implementierung von oben.
+	return ((a % m) + m) % m;
 }
diff --git a/math/rho.cpp b/math/rho.cpp
index 635c630..7885196 100644
--- a/math/rho.cpp
+++ b/math/rho.cpp
@@ -1,8 +1,8 @@
 using lll = __int128;
 ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim.
 	if (n % 2 == 0) return 2;
-	ll x = 0, y = 0, prd = 2;
-	auto f = [n](lll x){return (x * x) % n + 1;};
+	ll x = 0, y = 0, prd = 2, i = n/2 + 7;
+	auto f = [&](lll x){return (x * x + i) % n;};
 	for (ll t = 30, i = n/2 + 7; t % 40 || gcd(prd, n) == 1; t++) {
 		if (x == y) x = ++i, y = f(x);
 		if (ll q = (lll)prd * abs(x-y) % n; q) prd = q;
diff --git a/math/shortModInv.cpp b/math/shortModInv.cpp
index 747eb7a..244bacf 100644
--- a/math/shortModInv.cpp
+++ b/math/shortModInv.cpp
@@ -1,3 +1,3 @@
-ll inv(ll a, ll b){ // a^{-1} mod b
-    return 1 < a ? b - inv(b % a, a) * b / a : 1;
-}
\ No newline at end of file
+ll multInv(ll x, ll m) { // x^{-1} mod m
+    return 1 < x ? m - inv(m % x, x) * m / x : 1;
+}
diff --git a/math/tables/composite.tex b/math/tables/composite.tex
index b8f5428..8e14b2e 100644
--- a/math/tables/composite.tex
+++ b/math/tables/composite.tex
@@ -1,26 +1,27 @@
-\begin{tabularx}{\linewidth}{|r||r|r||r|}
+
+\begin{tabularx}{\linewidth}{|r||r|r||r|r|r||C|}
 	\hline
-	\multicolumn{4}{|c|}{Important Numbers} \\
+	\multicolumn{7}{|c|}{Important Numbers} \\
 	\hline
-	$10^x$ &          Highly Composite &      Divs &         Prime \\
+	$10^x$ &             Highly Composite &  \# Divs & $<$ Prime & $>$ Prime &                   \# Primes & \\
 	\hline
-	   $1$ &                       $6$ &       $4$ &  $10^{1}-~~3$ \\
-	   $2$ &                      $60$ &      $12$ &  $10^{2}-~~3$ \\
-	   $3$ &                     $840$ &      $32$ &  $10^{3}-~~3$ \\
-	   $4$ &                   $7~560$ &      $64$ &  $10^{4}- 27$ \\
-	   $5$ &                  $83~160$ &     $128$ &  $10^{5}-~~9$ \\
-	   $6$ &                 $720~720$ &     $240$ &  $10^{6}- 17$ \\
-	   $7$ &               $8~648~640$ &     $448$ &  $10^{7}-~~9$ \\
-	   $8$ &              $73~513~440$ &     $768$ &  $10^{8}- 11$ \\
-	   $9$ &             $735~134~400$ &   $1~344$ &  $10^{9}- 63$ \\
-	  $10$ &           $6~983~776~800$ &   $2~304$ & $10^{10}- 33$ \\
-	  $11$ &          $97~772~875~200$ &   $4~032$ & $10^{11}- 23$ \\
-	  $12$ &         $963~761~198~400$ &   $6~720$ & $10^{12}- 11$ \\
-	  $13$ &       $9~316~358~251~200$ &  $10~752$ & $10^{13}- 29$ \\
-	  $14$ &      $97~821~761~637~600$ &  $17~280$ & $10^{14}- 27$ \\
-	  $15$ &     $866~421~317~361~600$ &  $26~880$ & $10^{15}- 11$ \\
-	  $16$ &   $8~086~598~962~041~600$ &  $41~472$ & $10^{16}- 63$ \\
-	  $17$ &  $74~801~040~398~884~800$ &  $64~512$ & $10^{17}-~~3$ \\
-	  $18$ & $897~612~484~786~617~600$ & $103~680$ & $10^{18}- 11$ \\
+	     1 &                            6 &        4 &      $-3$ &      $+1$ &                           4 & \\
+	     2 &                           60 &       12 &      $-3$ &      $+1$ &                          25 & \\
+	     3 &                          840 &       32 &      $-3$ &      $+9$ &                         168 & \\
+	     4 &                       7\,560 &       64 &     $-27$ &      $+7$ &                      1\,229 & \\
+	     5 &                      83\,160 &      128 &      $-9$ &      $+3$ &                      9\,592 & \\
+	     6 &                     720\,720 &      240 &     $-17$ &      $+3$ &                     78\,498 & \\
+	     7 &                  8\,648\,640 &      448 &      $-9$ &     $+19$ &                    664\,579 & \\
+	     8 &                 73\,513\,440 &      768 &     $-11$ &      $+7$ &                 5\,761\,455 & \\
+	     9 &                735\,134\,400 &   1\,344 &     $-63$ &      $+7$ &                50\,847\,534 & \\
+	    10 &             6\,983\,776\,800 &   2\,304 &     $-33$ &     $+19$ &               455\,052\,511 & \\
+	    11 &            97\,772\,875\,200 &   4\,032 &     $-23$ &      $+3$ &            4\,118\,054\,813 & \\
+	    12 &           963\,761\,198\,400 &   6\,720 &     $-11$ &     $+39$ &           37\,607\,912\,018 & \\
+	    13 &        9\,316\,358\,251\,200 &  10\,752 &     $-29$ &     $+37$ &          346\,065\,536\,839 & \\
+	    14 &       97\,821\,761\,637\,600 &  17\,280 &     $-27$ &     $+31$ &       3\,204\,941\,750\,802 & \\
+	    15 &      866\,421\,317\,361\,600 &  26\,880 &     $-11$ &     $+37$ &      29\,844\,570\,422\,669 & \\
+	    16 &   8\,086\,598\,962\,041\,600 &  41\,472 &     $-63$ &     $+61$ &     279\,238\,341\,033\,925 & \\
+	    17 &  74\,801\,040\,398\,884\,800 &  64\,512 &      $-3$ &      $+3$ &  2\,623\,557\,157\,654\,233 & \\
+	    18 & 897\,612\,484\,786\,617\,600 & 103\,680 &     $-11$ &      $+3$ & 24\,739\,954\,287\,740\,860 & \\
 	\hline
 \end{tabularx}
diff --git a/math/transforms/seriesOperations.cpp b/math/transforms/seriesOperations.cpp
new file mode 100644
index 0000000..4743674
--- /dev/null
+++ b/math/transforms/seriesOperations.cpp
@@ -0,0 +1,56 @@
+vector<ll> poly_inv(const vector<ll>& a, int n) {
+	vector<ll> q = {powMod(a[0], mod-2, mod)};
+	for (int len = 1; len < n; len *= 2){
+		vector<ll> a2 = a, q2 = q;
+		a2.resize(2*len), q2.resize(2*len);
+		ntt(q2);
+		for (int j : {0, 1}) {
+			ntt(a2);
+			for (int i = 0; i < 2*len; i++) a2[i] = a2[i]*q2[i] % mod;
+			ntt(a2, true);
+			for (int i = 0; i < len; i++) a2[i] = 0;
+		}
+		for (int i = len; i < min(n, 2*len); i++) {
+			q.push_back((mod - a2[i]) % mod);
+	}}
+	return q;
+}
+
+vector<ll> poly_deriv(vector<ll> a) {
+	for (int i = 1; i < sz(a); i++)
+		a[i-1] = a[i] * i % mod;
+	a.pop_back();
+	return a;
+}
+
+vector<ll> poly_integr(vector<ll> a) {
+	if (a.empty()) return {0};
+	a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod);
+	for (int i = sz(a)-2; i > 0; i--)
+		a[i] = a[i-1] * powMod(i, mod-2, mod) % mod;
+	a[0] = 0;
+	return a;
+}
+
+vector<ll> poly_log(vector<ll> a, int n) {
+	a = mul(poly_deriv(a), poly_inv(a, n));
+	a.resize(n-1);
+	a = poly_integr(a);
+	return a;
+}
+
+vector<ll> poly_exp(vector<ll> a, int n) {
+	vector<ll> q = {1};
+	for (int len = 1; len < n; len *= 2) {
+		vector<ll> p = poly_log(q, 2*len);
+		for (int i = 0; i < 2*len; i++)
+			p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod;
+		vector<ll> q2 = q;
+		q2.resize(2*len);
+		ntt(p), ntt(q2);
+		for (int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod;
+		ntt(p, true);
+		for (int i = len; i < min(n, 2*len); i++) q.push_back(p[i]);
+	}
+	return q;
+}