diff options
Diffstat (limited to 'math')
| -rw-r--r-- | math/chineseRemainder.cpp | 14 | ||||
| -rw-r--r-- | math/linearRecurence.cpp | 32 | ||||
| -rw-r--r-- | math/math.tex | 295 | ||||
| -rw-r--r-- | math/rho.cpp | 5 | ||||
| -rw-r--r-- | math/transforms/all.cpp | 6 |
5 files changed, 193 insertions, 159 deletions
diff --git a/math/chineseRemainder.cpp b/math/chineseRemainder.cpp index 86a10ae..623f94b 100644 --- a/math/chineseRemainder.cpp +++ b/math/chineseRemainder.cpp @@ -1,14 +1,13 @@ -// 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, falls alle teilerfremd sind). +// 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 { using lll = __int128; vector<lll> lhs, rhs, mods, inv; lll M; // Produkt über die Moduli. Kann leicht überlaufen. - ll g(vector<lll> &vec) { + ll g(const vector<lll> &vec) { lll res = 0; for (int i = 0; i < sz(vec); i++) { res += (vec[i] * inv[i]) % M; @@ -24,8 +23,7 @@ struct ChineseRemainder { mods.push_back(m); } - // Löst das System. - ll solve() { + 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++) { diff --git a/math/linearRecurence.cpp b/math/linearRecurence.cpp new file mode 100644 index 0000000..83c4e05 --- /dev/null +++ b/math/linearRecurence.cpp @@ -0,0 +1,32 @@ +constexpr ll mod = 1000000007; +vector<ll> modMul(const vector<ll>& a, const vector<ll>& b, const vector<ll>& c) { + ll n = sz(c); + vector<ll> res(n * 2 + 1); + for (int i = 0; i <= n; i++) { //a*b + for (int j = 0; j <= n; j++) { + res[i + j] += a[i] * b[j]; + res[i + j] %= mod; + }} + for (int i = 2 * n; i > n; i--) { //res%c + for (int j = 0; j < n; j++) { + res[i - 1 - j] += res[i] * c[j]; + res[i - 1 - j] %= mod; + }} + res.resize(n + 1); + return res; +} + +ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) { + assert(sz(f) == sz(c)); + vector<ll> tmp(sz(c) + 1), a(sz(c) + 1); + tmp[0] = a[1] = 1; //tmp = (x^k) % c + + for (k++; k > 0; k /= 2) { + if (k & 1) tmp = modMul(tmp, a, c); + a = modMul(a, a, c); + } + + ll res = 0; + for (int i = 0; i < sz(c); i++) res += (tmp[i+1] * f[i]) % mod; + return res % mod; +} diff --git a/math/math.tex b/math/math.tex index feb0466..31fbdd6 100644 --- a/math/math.tex +++ b/math/math.tex @@ -1,38 +1,26 @@ \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}{Permutationen} - \begin{methods} - \method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)} - \end{methods} - \sourcecode{math/kthperm.cpp} - \begin{methods} - \method{permIndex}{bestimmt index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)} - \end{methods} - \sourcecode{math/permIndex.cpp} +\begin{algorithm}{Longest Increasing Subsequence} + \begin{itemize} + \item \code{lower\_bound} $\Rightarrow$ streng monoton + \item \code{upper\_bound} $\Rightarrow$ monoton + \end{itemize} + \sourcecode{math/longestIncreasingSubsequence.cpp} \end{algorithm} -\paragraph{Lemma von \textsc{Bézout}} -Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$. -Dann lassen sich wie folgt alle Lösungen berechnen: -\[ -\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right) -\] - -\paragraph{\textsc{Pell}-Gleichungen} -Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert. -Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen -sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: -\begin{align*} - x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\ - x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k -\end{align*} +\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$} +%\vspace{-1.25em} +%\begin{multicols}{2} +\method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)} +\sourcecode{math/modMulIterativ.cpp} +% \vfill\null\columnbreak +\method{powMod}{berechnet $a^b \bmod n$}{\log(b)} +\sourcecode{math/modPowIterativ.cpp} +%\end{multicols} +%\vspace{-2.75em} +\begin{itemize} + \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! +\end{itemize} \begin{algorithm}{ggT, kgV, erweiterter euklidischer Algorithmus} \runtime{\log(a) + \log(b)} @@ -49,7 +37,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: $\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$ - \end{itemize} +\end{itemize} \textbf{Sonst $\boldsymbol{\ggT(n, p) > 1}$:}\quad Es existiert kein $x^{-1}$. \sourcecode{math/multInv.cpp} @@ -62,38 +50,55 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/linearCongruence.cpp} \end{algorithm} -\subsection{Mod-Exponent und Multiplikation über $\boldsymbol{\mathbb{F}_p}$} -%\vspace{-1.25em} -%\begin{multicols}{2} - \method{mulMod}{berechnet $a \cdot b \bmod n$}{\log(b)} - \sourcecode{math/modMulIterativ.cpp} -% \vfill\null\columnbreak - \method{powMod}{berechnet $a^b \bmod n$}{\log(b)} - \sourcecode{math/modPowIterativ.cpp} -%\end{multicols} -%\vspace{-2.75em} -\begin{itemize} - \item für $a > 10^9$ \code{__int128} oder \code{modMul} benutzten! -\end{itemize} +\paragraph{Lemma von \textsc{Bézout}} +Sei $(x, y)$ eine Lösung der diophantischen Gleichung $ax + by = d$. +Dann lassen sich wie folgt alle Lösungen berechnen: +\[ +\left(x + k\frac{b}{\ggT(a, b)},~y - k\frac{a}{\ggT(a, b)}\right) +\] -\begin{algorithm}{Matrix-Exponent} +\paragraph{\textsc{Pell}-Gleichungen} +Sei $(\overline{x}, \overline{y})$ die Lösung von $x^2 - ny^2 = 1$, die $x>1$ minimiert. +Sei $(\tilde{x}, \tilde{y})$ die Lösung von $x^2-ny^2 = c$, die $x>1$ minimiert. Dann lassen +sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: +\begin{align*} + x_1&\coloneqq \tilde{x}, & y_1&\coloneqq\tilde{y}\\ + x_{k+1}&\coloneqq \overline{x}x_k+n\overline{y}y_k, & y_{k+1}&\coloneqq\overline{x}y_k+\overline{y}x_k +\end{align*} + + +\begin{algorithm}{Zykel Erkennung} \begin{methods} - \method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3} - \method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2} + \method{cycleDetection}{findet Zyklus von $x_0$ und Länge in $f$}{b+l} \end{methods} - \sourcecode{math/matrixPower.cpp} + \sourcecode{math/cycleDetection.cpp} \end{algorithm} -\begin{algorithm}{Berlekamp-Massey} +\begin{algorithm}{Permutationen} \begin{methods} - \method{BerlekampMassey}{Berechnet ein lineare Recurenz $n$-ter Ordnung}{n^2} - \method{}{aus den ersten $2n$ Werte}{} + \method{kthperm}{findet $k$-te Permutation \big($k \in [0, n!$)\big)}{n\*\log(n)} \end{methods} - \sourcecode{math/berlekampMassey.cpp} + \sourcecode{math/kthperm.cpp} + \begin{methods} + \method{permIndex}{bestimmt Index der Permutation \big($\mathit{res} \in [0, n!$)\big)}{n\*\log(n)} + \end{methods} + \sourcecode{math/permIndex.cpp} \end{algorithm} \begin{algorithm}{Lineare-Recurenz} - Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine Lineare Recurenz. Dann kann das \mbox{$k$-te} folgenglid in \runtime{n^3\log(k)} brechnet werden. + \begin{methods} + \method{BerlekampMassey}{Berechnet eine lineare Recurenz $n$-ter Ordnung}{n^2} + \method{}{aus den ersten $2n$ Werte}{} + \end{methods} + \sourcecode{math/berlekampMassey.cpp} + Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Recurenz. + + \begin{methods} + \method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $n$-ter Ordnung}{\log(k)\cdot n^2} + \end{methods} + \sourcecode{math/linearRecurence.cpp} + Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden: + \small $$\renewcommand\arraystretch{1.5} \setlength\arraycolsep{3pt} \begin{pmatrix} @@ -113,15 +118,24 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \end{pmatrix} ~~=~~ \begin{pmatrix} - f(n-1+k) \\ - f(n-2+k) \\ - \smash{\vdots} \\ - \smash{\vdots} \\ - f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\ + f(n-1+k) \\ + f(n-2+k) \\ + \smash{\vdots} \\ + \smash{\vdots} \\ + f(k) \makebox[0pt][l]{\hspace{15pt}$\vcenter{\hbox{\huge$\leftarrow$}}$}\\ \end{pmatrix} $$ \end{algorithm} + +\begin{algorithm}{Matrix-Exponent} + \begin{methods} + \method{precalc}{berechnet $m^{2^b}$ vor}{\log(b)\*n^3} + \method{calc}{berechnet $m^b_{y,x}$}{\log(b)\cdot n^2} + \end{methods} + \sourcecode{math/matrixPower.cpp} +\end{algorithm} + \begin{algorithm}{Chinesischer Restsatz} \begin{itemize} \item Extrem anfällig gegen Overflows. Evtl. häufig 128-Bit Integer verwenden. @@ -140,33 +154,42 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/chineseRemainder.cpp} \end{algorithm} -\begin{algorithm}{Primzahltest \& Faktorisierung} - \method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2} - \sourcecode{math/millerRabin.cpp} - \method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}3]{n}} - \sourcecode{math/rho.cpp} - %\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}} - %\sourcecode{math/squfof.cpp} +\begin{algorithm}{Teiler} + \begin{methods} + \method{countDivisors}{Zählt Teiler von $n$}{n^\frac{1}{3}} + \method{isPrime}{prüft ob Zahl prim ist}{1} + \end{methods} + \sourcecode{math/divisors.cpp} \end{algorithm} -\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}} +\begin{algorithm}{Primitivwurzeln} \begin{itemize} - \item Kann erweitert werden: Für jede Zahl den \{kleinsten, größten\} Primfaktor speichern, Liste von Primzahlen berechnen - \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung) + \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{primeSieve}{berechnet Primzahlen und Anzahl}{n\*\log(\log(n))} - \method{isPrime}{prüft ob Zahl prim ist}{1} + \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/primeSieve.cpp} + \sourcecode{math/primitiveRoot.cpp} \end{algorithm} -\begin{algorithm}{Teiler} +\begin{algorithm}{Diskreter Logarithmus} \begin{methods} - \method{countDivisors}{Zählt teiler von $n$}{n^\frac{1}{3}} - \method{isPrime}{prüft ob Zahl prim ist}{1} + \method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)} \end{methods} - \sourcecode{math/divisors.cpp} + \sourcecode{math/discreteLogarithm.cpp} +\end{algorithm} +%TODO +\begin{algorithm}{Diskrete \textrm{\textit{n}}-te Wurzel} + \begin{methods} + \method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)} + \end{methods} + Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$ + \sourcecode{math/discreteNthRoot.cpp} \end{algorithm} \subsection{Primzahlzählfunktion $\boldsymbol{\pi}$} @@ -176,23 +199,36 @@ 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} +\clearpage -\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion} -\begin{itemize} - \item Zählt die relativ primen Zahlen $\leq n$. +\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$} +\method{gauss}{löst LGS}{n^3} +\sourcecode{math/lgsFp.cpp} - \item Multiplikativ: - $\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$ +\subsection{LGS über $\boldsymbol{\mathbb{R}}$} +\sourcecode{math/gauss.cpp} - \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}{Primzahltest \& Faktorisierung} + \method{isPrime}{prüft ob Zahl prim ist}{\log(n)^2} + \sourcecode{math/millerRabin.cpp} + \method{rho}{findet zufälligen Teiler}{\sqrt[\leftroot{3}\uproot{2}4]{n}} + \sourcecode{math/rho.cpp} + %\method{squfof}{findet zufälligen Teiler}{\sqrt[\leftroot{4}\uproot{2}4]{n}} + %\sourcecode{math/squfof.cpp} +\end{algorithm} + +\begin{algorithm}{Primzahlsieb von \textsc{Eratosthenes}} + \begin{itemize} + \item Kann erweitert werden: Für jede Zahl den \{kleinsten, größten\} Primfaktor speichern, Liste von Primzahlen berechnen + \item Bis $10^8$ in unter 64MB Speicher (lange Berechnung) + \end{itemize} + \begin{methods} + \method{primeSieve}{berechnet Primzahlen und Anzahl}{n\*\log(\log(n))} + \method{isPrime}{prüft ob Zahl prim ist}{1} + \end{methods} + \sourcecode{math/primeSieve.cpp} +\end{algorithm} \begin{algorithm}{\textsc{Möbius}-Funktion und \textsc{Möbius}-Inversion} \begin{itemize} @@ -200,8 +236,8 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: Dann ist $f(n) = \sum_{d \vert n}g(d)\mu(\frac{n}{d})$. \item $\sum\limits_{d \vert n}\mu(d) = \begin{cases*} - 1 & falls $n = 1$\\ - 0 & sonst + 1 & falls $n = 1$\\ + 0 & sonst \end{cases*}$ \end{itemize} \textbf{Beispiel Inklusion/Exklusion:} @@ -212,43 +248,24 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: Die Anzahl der Subsequences mit $\ggT=1$ ist gegeben durch $\sum_{i = 1}^N \mu(i) \cdot (2^{cnt[i]} - 1)$. \sourcecode{math/mobius.cpp} \end{algorithm} +\clearpage -\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} +\subsection{\textsc{Euler}sche $\boldsymbol{\varphi}$-Funktion} +\begin{itemize} + \item Zählt die relativ primen Zahlen $\leq n$. -\begin{algorithm}{Diskreter Logarithmus} - \begin{methods} - \method{solve}{bestimmt Lösung $x$ für $a^x=b \bmod m$}{\sqrt{m}\*\log(m)} - \end{methods} - \sourcecode{math/discreteLogarithm.cpp} -\end{algorithm} -%TODO -\begin{algorithm}{Diskrete \textrm{\textit{n}}-te Wurzel} - \begin{methods} - \method{root}{bestimmt Lösung $x$ für $x^a=b \bmod m$ }{\sqrt{m}\*\log(m)} - \end{methods} - Alle Lösungen haben die Form $g^{c + \frac{i \cdot \phi(n)}{\gcd(a, \phi(n))}}$ - \sourcecode{math/discreteNthRoot.cpp} -\end{algorithm} + \item Multiplikativ: + $\gcd(a,b) = 1 \Longrightarrow \varphi(a) \cdot \varphi(b) = \varphi(ab)$ -\subsection{LGS über $\boldsymbol{\mathbb{F}_p}$} -\method{gauss}{löst LGS}{n^3} -\sourcecode{math/lgsFp.cpp} + \item $p$ prim, $k \in \mathbb{N}$: + $~\varphi(p^k) = p^k - p^{k - 1}$ -\subsection{LGS über $\boldsymbol{\mathbb{R}}$} -\sourcecode{math/gauss.cpp} + \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$. @@ -257,8 +274,8 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \item Vektoren \lstinline{a} und \lstinline{b} müssen mindestens Größe $\deg(A \cdot B) + 1$ haben. Größe muss eine Zweierpotenz sein. - \item Für ganzzahlige Koeffizienten: \lstinline{(int)round(real(a[i]))} - \item xor, or und and Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$ + \item Für ganzzahlige Koeffizienten: \lstinline{(ll)round(real(a[i]))} + \item \emph{xor}, \emph{or} und \emph{and} Transform funktioniert auch mit \code{double} oder modulo einer Primzahl $p$ falls $p \geq 2^{\texttt{bits}}$ \end{itemize} %\lstinputlisting{math/fft.cpp} %\lstinputlisting{math/ntt.cpp} @@ -278,14 +295,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch: \sourcecode{math/simpson.cpp} \end{algorithm} -\begin{algorithm}{Longest Increasing Subsequence} - \begin{itemize} - \item \code{lower\_bound} $\Rightarrow$ streng monoton - \item \code{upper\_bound} $\Rightarrow$ monoton - \end{itemize} - \sourcecode{math/longestIncreasingSubsequence.cpp} -\end{algorithm} - \begin{algorithm}{\textsc{Legendre}-Symbol} Sei $p \geq 3$ eine Primzahl, $a \in \mathbb{Z}$: \begin{align*} @@ -375,27 +384,27 @@ so gilt \[C_0 = 1\qquad C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} = \frac{1}{n + 1}\binom{2n}{n} = \frac{4n - 2}{n+1} \cdot C_{n-1}\] \begin{itemize} - \item Formel $1$ erlaubt berechnung ohne Division in \runtime{n^2} - \item Formel $2$ und $3$ erlauben berechnung in \runtime{n} + \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2} + \item Formel $2$ und $3$ erlauben Berechnung in \runtime{n} \end{itemize} \paragraph{\textsc{Euler}-Zahlen 1. Ordnung} Die Anzahl der Permutationen von $\{1, \ldots, n\}$ mit genau $k$ Anstiegen. Für die $n$-te Zahl gibt es $n$ mögliche Positionen zum Einfügen. -Dabei wird entweder ein Ansteig in zwei gesplitted oder ein Anstieg um $n$ ergänzt. +Dabei wird entweder ein Anstieg in zwei gesplitted oder ein Anstieg um $n$ ergänzt. \[\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \quad \eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1}= \sum_{i=0}^{k} (-1)^i\binom{n+1}{i}(k+1-i)^n\] \begin{itemize} - \item Formel $1$ erlaubt berechnung ohne Division in \runtime{n^2} - \item Formel $2$ erlaubt berechnung in \runtime{n\log(n)} + \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2} + \item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)} \end{itemize} \paragraph{\textsc{Euler}-Zahlen 2. Ordnung} Die Anzahl der Permutationen von $\{1,1, \ldots, n,n\}$ mit genau $k$ Anstiegen. \[\eulerII{n}{0} = 1 \qquad\eulerII{n}{n} = 0 \qquad\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}\] \begin{itemize} - \item Formel erlaubt berechnung ohne Division in \runtime{n^2} + \item Formel erlaubt Berechnung ohne Division in \runtime{n^2} \end{itemize} \paragraph{\textsc{Stirling}-Zahlen 1. Ordnung} @@ -416,13 +425,13 @@ Dazu kommt der Fall, dass die $n$ in ihrer eigenen Teilmenge (alleine) steht. \stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} = \frac{1}{k!} \sum\limits_{i=0}^{k} (-1)^{k-i}\binom{k}{i}i^n\] \begin{itemize} - \item Formel $1$ erlaubt berechnung ohne Division in \runtime{n^2} - \item Formel $2$ erlaubt berechnung in \runtime{n\log(n)} + \item Formel $1$ erlaubt Berechnung ohne Division in \runtime{n^2} + \item Formel $2$ erlaubt Berechnung in \runtime{n\log(n)} \end{itemize} \paragraph{\textsc{Bell}-Zahlen} Anzahl der Partitionen von $\{1, \ldots, n\}$. -Wie \textsc{Striling}-Zahlen 2. Ordnung ohne Limit durch $k$. +Wie \textsc{Stirling}-Zahlen 2. Ordnung ohne Limit durch $k$. \[B_1 = 1 \qquad B_n = \sum\limits_{k = 0}^{n - 1} B_k\binom{n-1}{k} = \sum\limits_{k = 0}^{n}\stirlingII{n}{k}\qquad\qquad B_{p^m+n}\equiv m\cdot B_n + B_{n+1} \bmod{p}\] diff --git a/math/rho.cpp b/math/rho.cpp index 1f5ba86..865a438 100644 --- a/math/rho.cpp +++ b/math/rho.cpp @@ -13,10 +13,7 @@ ll rho(ll n) { // Findet Faktor < n, nicht unbedingt prim. void factor(ll n, map<ll, int>& facts) { if (n == 1) return; - if (isPrime(n)) { - facts[n]++; - return; - } + if (isPrime(n)) {facts[n]++, return;} ll f = rho(n); factor(n / f, facts); factor(f, facts); diff --git a/math/transforms/all.cpp b/math/transforms/all.cpp index 4f4d83b..22cd5b5 100644 --- a/math/transforms/all.cpp +++ b/math/transforms/all.cpp @@ -24,8 +24,7 @@ void fft(vector<cplx>& a, bool inverse = 0) { t %= mod; a[j + k] = (u + t) % mod; a[j + s + k] = (u - t + mod) % mod; - w *= ws; - w %= mod;*/ + w = (w * ws) % mod;*/ /*ll u = a[j + k], t = a[j + s + k]; @\hl{xor only}@ a[j + k] = u + t; a[j + s + k] = u - t;*/ @@ -52,8 +51,7 @@ void fft(vector<cplx>& a, bool inverse = 0) { /*if (inverse) { @\hl{NTT only}@ ll div = powMod(n, mod - 2, mod); for (ll i = 0; i < n; i++) { - a[i] *= div; - a[i] %= mod; + a[i] = (a[i] * div) % mod; }}*/ /*if (inverse) { @\hl{xor only}@ for (ll i = 0; i < n; i++) { |