From 558aeeed893c98bf1851856c4effd1ac4c3722e7 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 8 May 2023 11:25:47 +0200
Subject: improved binomial

---
 math/binomial.cpp  |   9 ---------
 math/binomial0.cpp |  14 +++++++++++++
 math/binomial1.cpp |   9 +++++++++
 math/math.tex      |  58 ++++++++++++++++++++++++++++++-----------------------
 tcr.pdf            | Bin 669234 -> 652065 bytes
 5 files changed, 56 insertions(+), 34 deletions(-)
 delete mode 100644 math/binomial.cpp
 create mode 100644 math/binomial0.cpp
 create mode 100644 math/binomial1.cpp

diff --git a/math/binomial.cpp b/math/binomial.cpp
deleted file mode 100644
index 02b27e3..0000000
--- a/math/binomial.cpp
+++ /dev/null
@@ -1,9 +0,0 @@
-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;
-	}
-	return r;
-}
diff --git a/math/binomial0.cpp b/math/binomial0.cpp
new file mode 100644
index 0000000..d9af917
--- /dev/null
+++ b/math/binomial0.cpp
@@ -0,0 +1,14 @@
+constexpr ll lim = 10'000'000;
+ll fac[lim], inv[lim];
+
+void precalc() {
+	fac[0] = inv[0] = 1;
+	for (int i = 1; i < lim; i++) fac[i] = fac[i-1] * i % mod;
+	inv[lim - 1] = multInv(fac[lim - 1], mod);
+	for (int i = lim - 1; i > 0; i--) inv[i-1] = inv[i] * i % mod;
+}
+
+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;
+}
diff --git a/math/binomial1.cpp b/math/binomial1.cpp
new file mode 100644
index 0000000..02b27e3
--- /dev/null
+++ b/math/binomial1.cpp
@@ -0,0 +1,9 @@
+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;
+	}
+	return r;
+}
diff --git a/math/math.tex b/math/math.tex
index 54a44f7..1c3f856 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -398,8 +398,33 @@ so gilt
 	\binom{m}{n} \equiv \prod_{i=0}^k\binom{m_i}{n_i} \bmod{p}.
 \]
 
-\subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}
-\input{math/tables/twelvefold}
+%\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}
+		\method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
+	\end{methods}
+	\sourcecode{math/binomial1.cpp}
+	
+	\begin{methods}
+		\method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
+	\end{methods}
+	\sourcecode{math/binomial3.cpp}
+
+%	\begin{methods}
+%		\method{calc\_binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n}
+%	\end{methods}
+%	\textbf{WICHTIG:} braucht alle Primzahlen $\leq n$
+%	\sourcecode{math/binomial2.cpp}
+%\end{algorithm}
 
 \paragraph{\textsc{Catalan}-Zahlen}
 \begin{itemize}
@@ -455,6 +480,10 @@ Es gibt zwei Möglichkeiten für die $n$-te Zahl. Entweder sie bildet einen eige
 \begin{itemize}
 	\item Formel erlaubt berechnung ohne Division in \runtime{n^2}
 \end{itemize}
+\[\sum_{k=0}^{n}\pm\stirlingI{n}{k}x^k=x(x-1)(x-2)\cdots(x-n+1)\]
+\begin{itemize}
+	\item Berechne Polynom mit FFT und benutzte betrag der Koeffizienten \runtime{n\log(n)^2} (nur ungefähr gleich große Polynome zusammen multiplizieren beginnend mit $x-k$)
+\end{itemize}
 
 \paragraph{\textsc{Stirling}-Zahlen 2. Ordnung}
 Die Anzahl der Möglichkeiten $n$ Elemente in $k$ nichtleere Teilmengen zu zerlegen.
@@ -488,29 +517,8 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
 	\item Die Anzahl der Partitionen von $n$ in bis zu $k$ positive Summanden ist $\sum\limits_{i=0}^{k}p_i(n)=p_k(n+k)$.
 \end{itemize}
 
-\paragraph{Binomialkoeffizienten}
-Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.
-
-\textbf{WICHTIG:} Binomialkoeffizient in \runtime{1} berechnen indem man $x!$ vorberechnet.
-\columnbreak
-
-%\begin{algorithm}{Binomialkoeffizienten}
-	\begin{methods}
-		\method{calc\_binom}{berechnet Binomialkoeffizient $(n \le 61)$}{k}
-	\end{methods}
-	\sourcecode{math/binomial.cpp}
-
-	\begin{methods}
-		\method{calc\_binom}{berechnet Binomialkoeffizient modulo Primzahl $p$}{p-n}
-	\end{methods}
-	\sourcecode{math/binomial3.cpp}
-	
-	\begin{methods}
-		\method{calc\_binom}{berechnet Primfaktoren vom Binomialkoeffizient}{n}
-	\end{methods}
-	\textbf{WICHTIG:} braucht alle Primzahlen $\leq n$
-	\sourcecode{math/binomial2.cpp}
-%\end{algorithm}
+\subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}
+\input{math/tables/twelvefold}
 
 %\input{math/tables/numbers}
 
diff --git a/tcr.pdf b/tcr.pdf
index 13e9436..166de4d 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3