changes to bitwise convolutions

- modify or/and transform to remove unnecessary reversal
- or transform is now sum over subsets, add note about this
- remove old sum over subsets DP

1 files changed, 4 insertions, 2 deletions

diff --git a/content/math/math.tex b/content/math/math.tex
index d59da54..fdf7081 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -321,6 +321,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 \end{algorithm}

 

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

+	\label{fft}

 	Multipliziert Polynome $A$ und $B$.

 	\begin{itemize}

 		\item $\deg(A \cdot B) = \deg(A) + \deg(B)$

@@ -328,14 +329,15 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 		$\deg(A \cdot B) + 1$ haben.

 		Größe muss eine Zweierpotenz sein.

 		\item Für ganzzahlige Koeffizienten: \code{(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}}$

+		\item \emph{or} Transform berechnet sum over subsets

+			$\rightarrow$ inverse für inclusion/exclusion

 	\end{itemize}

 	%\sourcecode{math/fft.cpp}

 	%\sourcecode{math/ntt.cpp}

 	\sourcecode{math/transforms/fft.cpp}

 	\sourcecode{math/transforms/ntt.cpp}

 	\sourcecode{math/transforms/bitwiseTransforms.cpp}

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

+	Multiplikation mit 2 Transforms statt 3: (nur benutzen wenn nötig!)

 	\sourcecode{math/transforms/fftMul.cpp}

 \end{algorithm}