diff options
| -rw-r--r-- | math/binomial0.cpp | 14 | ||||
| -rw-r--r-- | math/binomial1.cpp (renamed from math/binomial.cpp) | 0 | ||||
| -rw-r--r-- | math/math.tex | 58 | ||||
| -rw-r--r-- | tcr.pdf | bin | 669234 -> 652065 bytes |
4 files changed, 47 insertions, 25 deletions
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/binomial.cpp b/math/binomial1.cpp index 02b27e3..02b27e3 100644 --- a/math/binomial.cpp +++ b/math/binomial1.cpp 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} |