summaryrefslogtreecommitdiff
path: root/content/math
diff options
context:
space:
mode:
Diffstat (limited to 'content/math')
-rw-r--r--content/math/divSum.cpp8
-rw-r--r--content/math/gauss.cpp12
-rw-r--r--content/math/lgsFp.cpp3
-rw-r--r--content/math/linearRecurrence.cpp53
-rw-r--r--content/math/linearRecurrenceOld.cpp33
-rw-r--r--content/math/math.tex90
-rw-r--r--content/math/minMod.cpp22
-rw-r--r--content/math/polynomial.cpp7
-rw-r--r--content/math/recover.cpp13
-rw-r--r--content/math/shortModInv.cpp2
-rw-r--r--content/math/squfof.cpp89
-rw-r--r--content/math/tables.tex22
-rw-r--r--content/math/tables/binom.tex31
-rw-r--r--content/math/tables/nim.tex5
-rw-r--r--content/math/tables/numbers.tex59
-rw-r--r--content/math/tables/platonic.tex26
-rw-r--r--content/math/tables/prime-composite.tex49
-rw-r--r--content/math/tables/probability.tex17
-rw-r--r--content/math/tables/series.tex32
-rw-r--r--content/math/tables/stuff.tex9
-rw-r--r--content/math/transforms/seriesOperations.cpp16
21 files changed, 273 insertions, 325 deletions
diff --git a/content/math/divSum.cpp b/content/math/divSum.cpp
new file mode 100644
index 0000000..48302b5
--- /dev/null
+++ b/content/math/divSum.cpp
@@ -0,0 +1,8 @@
+ll divSum(ll n, ll m, ll a, ll b){
+ if (m == 0) return 0;
+ ll ans = a/m * n*(n-1)/2 + b/m * n;
+ a %= m;
+ b %= m;
+ ll y = (a*(n-1)+b) / m;
+ return ans + y * (n-1) - divSum(y, a, m, m-b-1);
+}
diff --git a/content/math/gauss.cpp b/content/math/gauss.cpp
index 8129fd2..d431e52 100644
--- a/content/math/gauss.cpp
+++ b/content/math/gauss.cpp
@@ -14,19 +14,17 @@ void takeAll(int n, int line) {
int gauss(int n) {
vector<bool> done(n, false);
for (int i = 0; i < n; i++) {
- int swappee = i; // Sucht Pivotzeile für bessere Stabilität.
- for (int j = 0; j < n; j++) {
- if (done[j]) continue;
- if (abs(mat[j][i]) > abs(mat[i][i])) swappee = j;
+ int j = i; // Sucht Pivotzeile für bessere Stabilität.
+ for (int k = 0; k < n; k++) {
+ if (!done[k] && abs(mat[k][i]) > abs(mat[i][i])) j = k;
}
- swap(mat[i], mat[swappee]);
+ swap(mat[i], mat[j]);
if (abs(mat[i][i]) > EPS) {
normalLine(i);
takeAll(n, i);
done[i] = true;
}}
- // Ab jetzt nur checks bzgl. Eindeutigkeit/Existenz der Lösung.
- for (int i = 0; i < n; i++) {
+ for (int i = 0; i < n; i++) { // gauss fertig, prüfe Lösung
bool allZero = true;
for (int j = i; j < n; j++) allZero &= abs(mat[i][j]) <= EPS;
if (allZero && abs(mat[i][n]) > EPS) return INCONSISTENT;
diff --git a/content/math/lgsFp.cpp b/content/math/lgsFp.cpp
index 0241742..bf18c86 100644
--- a/content/math/lgsFp.cpp
+++ b/content/math/lgsFp.cpp
@@ -22,5 +22,4 @@ void gauss(int n, ll mod) {
normalLine(i, mod);
takeAll(n, i, mod);
done[i] = true;
-}}
-// für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@
+}} // für Eindeutigkeit, Existenz etc. siehe LGS über R @\sourceref{math/gauss.cpp}@
diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp
index 2501e64..a8adacd 100644
--- a/content/math/linearRecurrence.cpp
+++ b/content/math/linearRecurrence.cpp
@@ -1,33 +1,30 @@
-constexpr ll mod = 1'000'000'007;
-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;
+constexpr ll mod = 998244353;
+// oder ntt mul @\sourceref{math/transforms/ntt.cpp}@
+vector<ll> mul(const vector<ll>& a, const vector<ll>& b) {
+ vector<ll> c(sz(a) + sz(b) - 1);
+ for (int i = 0; i < sz(a); i++) {
+ for (int j = 0; j < sz(b); j++) {
+ c[i+j] += a[i]*b[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;
+ for (ll& x : c) x %= mod;
+ return c;
}
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;
+ int n = sz(c);
+ vector<ll> q(n + 1, 1);
+ for (int i = 0; i < n; i++) q[i + 1] = (mod - c[i]) % mod;
+ vector<ll> p = mul(f, q);
+ p.resize(n);
+ p.push_back(0);
+ do {
+ vector<ll> q2 = q;
+ for (int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod;
+ vector<ll> x = mul(p, q2), y = mul(q, q2);
+ for (int i = 0; i <= n; i++){
+ p[i] = i == n ? 0 : x[2*i + (k&1)];
+ q[i] = y[2*i];
+ }
+ } while (k /= 2);
+ return p[0];
}
diff --git a/content/math/linearRecurrenceOld.cpp b/content/math/linearRecurrenceOld.cpp
new file mode 100644
index 0000000..2501e64
--- /dev/null
+++ b/content/math/linearRecurrenceOld.cpp
@@ -0,0 +1,33 @@
+constexpr ll mod = 1'000'000'007;
+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/content/math/math.tex b/content/math/math.tex
index f670a70..644fbc8 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -109,8 +109,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
\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}{Teiler}
@@ -138,8 +136,9 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
Sei $f(n)=c_{0}f(n-1)+c_{1}f(n-2)+\dots + c_{n-1}f(0)$ eine lineare Rekurrenz.
\begin{methods}
- \method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot n^2}
+ \method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot \text{mul}(n)}
\end{methods}
+ Die Polynom-Multiplikation kann auch mit NTT gemacht werden!
\sourcecode{math/linearRecurrence.cpp}
Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:
$$\renewcommand\arraystretch{1.5}
@@ -308,7 +307,10 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
\method{gauss}{löst LGS}{n^3}
\sourcecode{math/gauss.cpp}
-\vfill\null\columnbreak
+\begin{algorithm}{Inversionszahl}
+ \vspace{-2pt}
+ \sourcecode{math/inversions.cpp}
+\end{algorithm}
\begin{algorithm}{Numerisch Extremstelle bestimmen}
\sourcecode{math/goldenSectionSearch.cpp}
@@ -318,7 +320,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
\sourcecode{math/simpson.cpp}
\end{algorithm}
-
\begin{algorithm}{Polynome, FFT, NTT \& andere Transformationen}
Multipliziert Polynome $A$ und $B$.
\begin{itemize}
@@ -342,21 +343,6 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
\sourcecode{math/transforms/seriesOperations.cpp}
\end{algorithm}
-\begin{algorithm}{Inversionszahl}
- \sourcecode{math/inversions.cpp}
-\end{algorithm}
-
-\subsection{Satz von \textsc{Sprague-Grundy}}
-Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
-\[
-g\left(X\right) := \min\left\{
-\mathbb{Z}_0^+ \setminus
-\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}
-\right\}
-\]
-$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\
-Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.
-
\subsection{Kombinatorik}
\paragraph{\textsc{Wilson}'s Theorem}
@@ -389,7 +375,9 @@ so gilt
%\begin{algorithm}{Binomialkoeffizienten}
\paragraph{Binomialkoeffizienten}
Die Anzahl der \mbox{$k$-elementigen} Teilmengen einer \mbox{$n$-elementigen} Menge.
-
+
+ \input{math/tables/binom}
+
\begin{methods}
\method{precalc}{berechnet $n!$ und $n!^{-1}$ vor}{\mathit{lim}}
\method{calc\_binom}{berechnet Binomialkoeffizient}{1}
@@ -498,7 +486,7 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
\begin{align*}
p_0(0)=1 \qquad p_k(n)&=0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0\\
p_k(n)&= p_k(n-k) + p_{k-1}(n-1)\\[2pt]
- p(n)&=\sum_{k=1}^{n} p_k(n)=p_n(2n)=\sum\limits_{k\neq0}^\infty(-1)^{k+1}p\bigg(n - \frac{k(3k-1)}{2}\bigg)
+ p(n)=\sum_{k=1}^{n} p_k(n)&=p_n(2n)=\sum\limits_{k=1}^\infty(-1)^{k+1}\bigg[p\bigg(n - \frac{k(3k-1)}{2}\bigg) + p\bigg(n - \frac{k(3k+1)}{2}\bigg)\bigg]
\end{align*}
\begin{itemize}
\item in Formel $3$ kann abgebrochen werden wenn $\frac{k(3k-1)}{2} > n$.
@@ -508,6 +496,59 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
\subsection{The Twelvefold Way \textnormal{(verteile $n$ Bälle auf $k$ Boxen)}}
\input{math/tables/twelvefold}
+\subsection{Platonische Körper}
+\input{math/tables/platonic}
+
+\input{math/tables/probability}
+
+\subsection{Satz von \textsc{Sprague-Grundy}}
+Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu:
+\[
+g\left(X\right) := \min\left\{
+\mathbb{Z}_0^+ \setminus
+\left\{g\left(Y\right) \mid Y \text{ von } X \text{ aus direkt erreichbar}\right\}
+\right\}
+\]
+$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\
+Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$.
+
+\subsection{Nim-Spiele}
+\begin{itemize}
+ \item[\ding{182}] letzter gewinnt (normal)
+ \item[\ding{183}] letzter verliert
+\end{itemize}
+\input{math/tables/nim}
+
+\subsection{Verschiedenes}
+\input{math/tables/stuff}
+
+\begin{algorithm}{Div Sum}
+ \method{divSum}{berechnet $\sum_{i=0}^{n-1} \left\lfloor \frac{a\cdot i + b}{m} \right\rfloor$}{\log(n)}
+ \textbf{Wichtig:} $b$ darf nicht negativ sein!
+ \sourcecode{math/divSum.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Min Mod}
+ \begin{methods}
+ \method{firstVal}{berechnet den ersten Wert von $0,\ a, \ldots,\ a \cdot i \bmod{m}$,}{\log(m)}
+ \method{}{der in $[l, r]$ liegt. Gibt $-1$ zurück, falls er nicht existiert.}{}
+ \method{minMod}{berechnet das Minimum von $(a \cdot i + b) \bmod{m}$ für $i \in [0, n)$}{\log(m)}
+ \end{methods}
+ \textbf{Wichtig:} $0 \leq a, b, l, r < m$
+ \sourcecode{math/minMod.cpp}
+\end{algorithm}
+
+\subsection{Reihen}
+\input{math/tables/series}
+
+\subsection{Wichtige Zahlen}
+\input{math/tables/prime-composite}
+
+\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }
+\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}
+\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
+\sourcecode{math/recover.cpp}
+
\optional{
\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
\begin{methods}
@@ -516,9 +557,10 @@ Die Anzahl der Partitionen von $n$ mit Elementen aus ${1,\dots,k}$.
\method{pi}{zählt Primzahlen $\leq n$ ($n < N^2$)}{n^{2/3}}
\end{methods}
\sourcecode{math/piLehmer.cpp}
-}
-%\input{math/tables/numbers}
+\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
+\sourcecode{math/piLegendre.cpp}
+}
\begin{algorithm}[optional]{Big Integers}
\sourcecode{math/bigint.cpp}
diff --git a/content/math/minMod.cpp b/content/math/minMod.cpp
new file mode 100644
index 0000000..a80e783
--- /dev/null
+++ b/content/math/minMod.cpp
@@ -0,0 +1,22 @@
+ll firstVal(ll a, ll m, ll l, ll r) {
+ if (l == 0) return 0;
+ if (a == 0) return -1;
+ if ((l-1)/a < r/a) return (l+a-1) / a*a;
+ ll s = (r+a-1) / a*a;
+ ll v = firstVal(m % a, a, s-r, s-l);
+ return v < 0 ? -1 : s - v;
+}
+
+ll minMod(ll n, ll m, ll a, ll b) {
+ if (a == 0) return b;
+ ll g = gcd(m, a);
+ ll c = b % g;
+ m /= g;
+ a /= g;
+ b /= g;
+ ll ai = multInv(a, m);
+ ll l = ai*b % m;
+ ll r = (n-1 + ai*b) % m;
+ if (n >= m || l > r) return c;
+ return a * firstVal(ai, m, l, r) % m * g + c;
+} \ No newline at end of file
diff --git a/content/math/polynomial.cpp b/content/math/polynomial.cpp
index 44f6207..84f3aaa 100644
--- a/content/math/polynomial.cpp
+++ b/content/math/polynomial.cpp
@@ -1,7 +1,7 @@
struct poly {
vector<ll> data;
- poly(int deg = 0) : data(max(1, deg)) {}
+ poly(int deg = 0) : data(1 + deg) {}
poly(initializer_list<ll> _data) : data(_data) {}
int size() const {return sz(data);}
@@ -40,17 +40,18 @@ struct poly {
//return p(x+a)
poly operator<<(ll a) const {
- poly res(size());
+ poly res(size() - 1);
for (int i = size() - 1; i >= 0; i--) {
for (int j = size() - i - 1; j >= 1; j--)
res[j] = (res[j] * a + res[j - 1]) % mod;
- res[0] = (res[0] * a + res[i]) % mod;
+ res[0] = (res[0] * a + data[i]) % mod;
}
return res;
}
pair<poly, poly> divmod(const poly& d) const {
int i = size() - d.size();
+ if (i <= 0) return {{}, *this};
poly s(i + 1), r = *this;
ll inv = multInv(d.data.back(), mod);
for (; i >= 0; i--) {
diff --git a/content/math/recover.cpp b/content/math/recover.cpp
new file mode 100644
index 0000000..1a593f0
--- /dev/null
+++ b/content/math/recover.cpp
@@ -0,0 +1,13 @@
+ll sq(ll x) {return x*x;}
+
+array<ll, 2> recover(ll c, ll m) {
+ array<ll, 2> u = {m, 0}, v = {c, 1};
+ while (m <= 2 * sq(v[0])) {
+ ll q = u[0] / v[0];
+ u[0] -= q * v[0];
+ u[1] -= q * v[1];
+ swap(u, v);
+ }
+ if (v[1] <= 0 || 2 * sq(v[1]) >= m) return {-1, -1};
+ return v;
+}
diff --git a/content/math/shortModInv.cpp b/content/math/shortModInv.cpp
index f696cce..cf91ca0 100644
--- a/content/math/shortModInv.cpp
+++ b/content/math/shortModInv.cpp
@@ -1,3 +1,3 @@
ll multInv(ll x, ll m) { // x^{-1} mod m
- return 1 < x ? m - multInv(m % x, x) * m / x : 1;
+ return 1 < x ? m - multInv(m % x, x) * m / x : 1;
}
diff --git a/content/math/squfof.cpp b/content/math/squfof.cpp
deleted file mode 100644
index 1cb97de..0000000
--- a/content/math/squfof.cpp
+++ /dev/null
@@ -1,89 +0,0 @@
-using lll = __int128;
-
-constexpr lll multipliers[] = {1, 3, 5, 7,
- 11, 3*5, 3*7, 3*11,
- 5*7, 5*11, 7*11,
- 3*5*7, 3*5*11, 3*7*11,
- 5*7*11, 3*5*7*11};
-
-lll root(lll x) {
- lll r = sqrtl(x);
- while(r*r < x) r++;
- while(r*r > x) r--;
- return r;
-}
-
-lll croot(lll x) {
- lll r = cbrtl(x);
- while(r*r*r < x) r++;
- while(r*r*r > x) r--;
- return r;
-}
-
-lll squfof(lll N) {
- lll s = croot(N);
- if (s*s*s == N) return s;
- s = root(N);
- if (s*s == N) return s;
- for (lll k : multipliers) {
- lll D = k * N;
- lll Po, P, Pprev, q, b, r, i;
- Po = Pprev = P = root(D);
- lll Qprev = 1;
- lll Q = D - Po*Po;
- lll L = 2 * root(2 * s);
- lll B = 3 * L;
- for (i = 2; i < B; i++) {
- b = (Po + P) / Q;
- P = b*Q - P;
- q = Q;
- Q = Qprev + b * (Pprev - P);
- r = root(Q);
- if (!(i & 1) && r*r == Q) break;
- Qprev = q;
- Pprev = P;
- }
- if (i >= B) continue;
- b = (Po - P) / r;
- Pprev = P = b*r + P;
- Qprev = r;
- Q = (D-Pprev*Pprev)/Qprev;
- i = 0;
- do {
- b = (Po + P) / Q;
- Pprev = P;
- P = b*Q - P;
- q = Q;
- Q = Qprev + b * (Pprev - P);
- Qprev = q;
- i++;
- } while(P != Pprev);
- r = gcd(N, Qprev);
- if (r != 1 && r != N) return r;
- }
- exit(1);//try fallback to pollard rho
-}
-
-constexpr lll trialLim = 5'000;
-
-void factor(lll n, map<lll, int>& facts) {
- for (lll i = 2; i * i <= n && i <= trialLim; i++) {
- while (n % i == 0) {
- facts[i]++;
- n /= i;
- }}
- if (n > 1 && n < trialLim * trialLim) {
- facts[n]++;
- } else {
- vector<lll> todo = {n};
- while (!todo.empty()) {
- lll c = todo.back();
- todo.pop_back();
- if (c == 1) continue;
- if (isPrime(c)) {
- facts[c]++;
- } else {
- lll d = squfof(c);
- todo.push_back(d);
- todo.push_back(c / d);
-}}}}
diff --git a/content/math/tables.tex b/content/math/tables.tex
deleted file mode 100644
index c422d73..0000000
--- a/content/math/tables.tex
+++ /dev/null
@@ -1,22 +0,0 @@
-\enlargethispage{0.2cm}
-\begin{multicols*}{2}
- \refstepcounter{subsection}
- \subsectionmark{Tables}
- \addcontentsline{toc}{subsection}{\protect\numberline{\thesubsection}Tables}
-
- \input{math/tables/binom}
- \vfill
- \input{math/tables/prime-composite}
- \vfill
- \input{math/tables/platonic}
- \vfill
- \input{math/tables/series}
-
- \columnbreak
-
- \input{math/tables/probability}
- \vfill
- \input{math/tables/stuff}
- \vfill
- \input{math/tables/nim}
-\end{multicols*}
diff --git a/content/math/tables/binom.tex b/content/math/tables/binom.tex
index 878a6b0..9fc9ae3 100644
--- a/content/math/tables/binom.tex
+++ b/content/math/tables/binom.tex
@@ -1,28 +1,27 @@
-\begin{tabularx}{\linewidth}{|XXXX|}
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|C|}
\hline
- \multicolumn{4}{|c|}{Binomialkoeffizienten} \\
- \hline
- \multicolumn{4}{|c|}{
$\frac{n!}{k!(n - k)!} \hfill=\hfill
\binom{n}{k} \hfill=\hfill
\binom{n}{n - k} \hfill=\hfill
\frac{n}{k}\binom{n - 1}{k - 1} \hfill=\hfill
\frac{n-k+1}{k}\binom{n}{k - 1} \hfill=\hfill
- \binom{n - 1}{k} + \binom{n - 1}{k - 1} \hfill=\hfill
+ \frac{k+1}{n-k}\binom{n}{k + 1} \hfill=\hfill$\\
+
+ $\binom{n - 1}{k - 1} + \binom{n - 1}{k} \hfill=\hfill
+ \binom{n + 1}{k + 1} - \binom{n}{k + 1} \hfill=\hfill
(-1)^k \binom{k - n - 1}{k} \hfill\approx\hfill
- 2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$
- } \\
+ 2^{n} \cdot \frac{2}{\sqrt{2\pi n}}\cdot\exp\left(-\frac{2(x - \frac{n}{2})^2}{n}\right)$\\
\grayhline
- $\sum\limits_{k = 0}^n \binom{n}{k} = 2^n$ &
- $\sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}$ &
- $\sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}$ &
- $\sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\
+ $\sum\limits_{k = 0}^n \binom{n}{k} = 2^n\hfill
+ \sum\limits_{k = 0}^n \binom{k}{m} = \binom{n + 1}{m + 1}\hfill
+ \sum\limits_{i = 0}^n \binom{n}{i}^2 = \binom{2n}{n}\hfill
+ \sum\limits_{k = 0}^n\binom{r + k}{k} = \binom{r + n + 1}{n}$\\
- $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}$ &
- $\sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}$ &
- \multicolumn{2}{l|}{
- $\sum\limits_{i = 1}^n \binom{n}{i} F_i = F_{2n} \quad F_n = n\text{-th Fib.}$
- }\\
+ $\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}\hfill
+ \sum\limits_{k = 0}^n \binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}\hfill
+ \sum\limits_{i = 1}^n \binom{n}{i} \mathit{Fib}_i = \mathit{Fib}_{2n}$\\
\hline
\end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/nim.tex b/content/math/tables/nim.tex
index 8490d42..66e289e 100644
--- a/content/math/tables/nim.tex
+++ b/content/math/tables/nim.tex
@@ -1,7 +1,6 @@
+\begin{expandtable}
\begin{tabularx}{\linewidth}{|p{0.37\linewidth}|X|}
\hline
- \multicolumn{2}{|c|}{Nim-Spiele (\ding{182} letzter gewinnt (normal), \ding{183} letzter verliert)} \\
- \hline
Beschreibung &
Strategie \\
\hline
@@ -94,3 +93,5 @@
Periode ab $n = 72$ der Länge $12$.\\
\hline
\end{tabularx}
+\end{expandtable}
+ \ No newline at end of file
diff --git a/content/math/tables/numbers.tex b/content/math/tables/numbers.tex
deleted file mode 100644
index 1dc9f38..0000000
--- a/content/math/tables/numbers.tex
+++ /dev/null
@@ -1,59 +0,0 @@
-\begin{expandtable}
-\begin{tabularx}{\linewidth}{|l|X|}
- \hline
- \multicolumn{2}{|c|}{Berühmte Zahlen} \\
- \hline
- \textsc{Fibonacci} &
- $f(0) = 0 \quad
- f(1) = 1 \quad
- f(n+2) = f(n+1) + f(n)$ \\
- \grayhline
-
- \textsc{Catalan} &
- $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{2(2n - 1)}{n+1} \cdot C_{n-1}$ \\
- \grayhline
-
- \textsc{Euler} I &
- $\eulerI{n}{0} = \eulerI{n}{n-1} = 1 \qquad
- \eulerI{n}{k} = (k+1) \eulerI{n-1}{k} + (n-k) \eulerI{n-1}{k-1} $ \\
- \grayhline
-
- \textsc{Euler} II &
- $\eulerII{n}{0} = 1 \quad
- \eulerII{n}{n} = 0 \quad$\\
- & $\eulerII{n}{k} = (k+1) \eulerII{n-1}{k} + (2n-k-1) \eulerII{n-1}{k-1}$ \\
- \grayhline
-
- \textsc{Stirling} I &
- $\stirlingI{0}{0} = 1 \qquad
- \stirlingI{n}{0} = \stirlingI{0}{n} = 0 \qquad
- \stirlingI{n}{k} = \stirlingI{n-1}{k-1} + (n-1) \stirlingI{n-1}{k}$ \\
- \grayhline
-
- \textsc{Stirling} II &
- $\stirlingII{n}{1} = \stirlingII{n}{n} = 1 \qquad
- \stirlingII{n}{k} = k \stirlingII{n-1}{k} + \stirlingII{n-1}{k-1} =
- \frac{1}{k!} \sum\limits_{j=0}^{k} (-1)^{k-j}\binom{k}{j}j^n$\\
- \grayhline
-
- \textsc{Bell} &
- $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}$\\
- \grayhline
-
- \textsc{Partitions} &
- $p(0,0) = 1 \quad
- p(n,k) = 0 \text{ für } k > n \text{ oder } n \leq 0 \text{ oder } k \leq 0$ \\
- & $p(n,k) = p(n-k,k) + p(n-1,k-1)$\\
- \grayhline
-
- \textsc{Partitions} &
- $f(0) = 1 \quad f(n) = 0~(n < 0)$ \\
- & $f(n)=\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k+1)}{2})+\sum\limits_{k=1}^\infty(-1)^{k-1}f(n - \frac{k(3k-1)}{2})$\\
-
- \hline
-\end{tabularx}
-\end{expandtable}
diff --git a/content/math/tables/platonic.tex b/content/math/tables/platonic.tex
index f4ee554..2866ccf 100644
--- a/content/math/tables/platonic.tex
+++ b/content/math/tables/platonic.tex
@@ -1,39 +1,39 @@
+\begin{expandtable}
\begin{tabularx}{\linewidth}{|X|CCCX|}
\hline
- \multicolumn{5}{|c|}{Platonische Körper} \\
- \hline
- Übersicht & Seiten & Ecken & Kanten & dual zu \\
+ Übersicht & |F| & |V| & |E| & dual zu \\
\hline
Tetraeder & 4 & 4 & 6 & Tetraeder \\
- Würfel/Hexaeder & 6 & 8 & 12 & Oktaeder \\
- Oktaeder & 8 & 6 & 12 & Würfel/Hexaeder\\
+ Würfel & 6 & 8 & 12 & Oktaeder \\
+ Oktaeder & 8 & 6 & 12 & Würfel\\
Dodekaeder & 12 & 20 & 30 & Ikosaeder \\
Ikosaeder & 20 & 12 & 30 & Dodekaeder \\
\hline
\multicolumn{5}{|c|}{Färbungen mit maximal $n$ Farben (bis auf Isomorphie)} \\
\hline
- \multicolumn{3}{|l}{Ecken vom Oktaeder/Seiten vom Würfel} &
+ \multicolumn{3}{|l}{|V| vom Oktaeder/|F| vom Würfel} &
\multicolumn{2}{l|}{$(n^6 + 3n^4 + 12n^3 + 8n^2)/24$} \\
- \multicolumn{3}{|l}{Ecken vom Würfel/Seiten vom Oktaeder} &
+ \multicolumn{3}{|l}{|V| vom Würfel/|F| vom Oktaeder} &
\multicolumn{2}{l|}{$(n^8 + 17n^4 + 6n^2)/24$} \\
- \multicolumn{3}{|l}{Kanten vom Würfel/Oktaeder} &
+ \multicolumn{3}{|l}{|E| vom Würfel/Oktaeder} &
\multicolumn{2}{l|}{$(n^{12} + 6n^7 + 3n^6 + 8n^4 + 6n^3)/24$} \\
- \multicolumn{3}{|l}{Ecken/Seiten vom Tetraeder} &
+ \multicolumn{3}{|l}{|V|/|F| vom Tetraeder} &
\multicolumn{2}{l|}{$(n^4 + 11n^2)/12$} \\
- \multicolumn{3}{|l}{Kanten vom Tetraeder} &
+ \multicolumn{3}{|l}{|E| vom Tetraeder} &
\multicolumn{2}{l|}{$(n^6 + 3n^4 + 8n^2)/12$} \\
- \multicolumn{3}{|l}{Ecken vom Ikosaeder/Seiten vom Dodekaeder} &
+ \multicolumn{3}{|l}{|V| vom Ikosaeder/|F| vom Dodekaeder} &
\multicolumn{2}{l|}{$(n^{12} + 15n^6 + 44n^4)/60$} \\
- \multicolumn{3}{|l}{Ecken vom Dodekaeder/Seiten vom Ikosaeder} &
+ \multicolumn{3}{|l}{|V| vom Dodekaeder/|F| vom Ikosaeder} &
\multicolumn{2}{l|}{$(n^{20} + 15n^{10} + 20n^8 + 24n^4)/60$} \\
- \multicolumn{3}{|l}{Kanten vom Dodekaeder/Ikosaeder (evtl. falsch)} &
+ \multicolumn{3}{|l}{|E| vom Dodekaeder/Ikosaeder} &
\multicolumn{2}{l|}{$(n^{30} + 15n^{16} + 20n^{10} + 24n^6)/60$} \\
\hline
\end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/prime-composite.tex b/content/math/tables/prime-composite.tex
index 99b3348..073b4ba 100644
--- a/content/math/tables/prime-composite.tex
+++ b/content/math/tables/prime-composite.tex
@@ -1,26 +1,31 @@
-\begin{tabularx}{\linewidth}{|r|r|rIr|rIrIr|C|}
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|r|rIr|rIr|r|r|}
\hline
- \multicolumn{8}{|c|}{Important Numbers} \\
+ \multirow{2}{*}{$10^x$}
+ & \multirow{2}{*}{Highly Composite}
+ & \multirow{2}{*}{\# Divs}
+ & \multicolumn{2}{|c|}{Prime}
+ & \multirow{2}{*}{\# Primes} & \multirow{2}{*}{Primorial} \\
+ & & & $<$ & $>$ & & \\
\hline
- $10^x$ & Highly Composite & \# Divs & $<$ Prime & $>$ Prime & \# Primes & primorial & \\
- \hline
- 1 & 6 & 4 & $-3$ & $+1$ & 4 & 2 & \\
- 2 & 60 & 12 & $-3$ & $+1$ & 25 & 3 & \\
- 3 & 840 & 32 & $-3$ & $+9$ & 168 & 4 & \\
- 4 & 7\,560 & 64 & $-27$ & $+7$ & 1\,229 & 5 & \\
- 5 & 83\,160 & 128 & $-9$ & $+3$ & 9\,592 & 6 & \\
- 6 & 720\,720 & 240 & $-17$ & $+3$ & 78\,498 & 7 & \\
- 7 & 8\,648\,640 & 448 & $-9$ & $+19$ & 664\,579 & 8 & \\
- 8 & 73\,513\,440 & 768 & $-11$ & $+7$ & 5\,761\,455 & 8 & \\
- 9 & 735\,134\,400 & 1\,344 & $-63$ & $+7$ & 50\,847\,534 & 9 & \\
- 10 & 6\,983\,776\,800 & 2\,304 & $-33$ & $+19$ & 455\,052\,511 & 10 & \\
- 11 & 97\,772\,875\,200 & 4\,032 & $-23$ & $+3$ & 4\,118\,054\,813 & 10 & \\
- 12 & 963\,761\,198\,400 & 6\,720 & $-11$ & $+39$ & 37\,607\,912\,018 & 11 & \\
- 13 & 9\,316\,358\,251\,200 & 10\,752 & $-29$ & $+37$ & 346\,065\,536\,839 & 12 & \\
- 14 & 97\,821\,761\,637\,600 & 17\,280 & $-27$ & $+31$ & 3\,204\,941\,750\,802 & 12 & \\
- 15 & 866\,421\,317\,361\,600 & 26\,880 & $-11$ & $+37$ & 29\,844\,570\,422\,669 & 13 & \\
- 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & $-63$ & $+61$ & 279\,238\,341\,033\,925 & 13 & \\
- 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & $-3$ & $+3$ & 2\,623\,557\,157\,654\,233 & 14 & \\
- 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & 16 & \\
+ 1 & 6 & 4 & $-3$ & $+1$ & 4 & 2 \\
+ 2 & 60 & 12 & $-3$ & $+1$ & 25 & 3 \\
+ 3 & 840 & 32 & $-3$ & $+9$ & 168 & 4 \\
+ 4 & 7\,560 & 64 & $-27$ & $+7$ & 1\,229 & 5 \\
+ 5 & 83\,160 & 128 & $-9$ & $+3$ & 9\,592 & 6 \\
+ 6 & 720\,720 & 240 & $-17$ & $+3$ & 78\,498 & 7 \\
+ 7 & 8\,648\,640 & 448 & $-9$ & $+19$ & 664\,579 & 8 \\
+ 8 & 73\,513\,440 & 768 & $-11$ & $+7$ & 5\,761\,455 & 8 \\
+ 9 & 735\,134\,400 & 1\,344 & $-63$ & $+7$ & 50\,847\,534 & 9 \\
+ 10 & 6\,983\,776\,800 & 2\,304 & $-33$ & $+19$ & 455\,052\,511 & 10 \\
+ 11 & 97\,772\,875\,200 & 4\,032 & $-23$ & $+3$ & 4\,118\,054\,813 & 10 \\
+ 12 & 963\,761\,198\,400 & 6\,720 & $-11$ & $+39$ & 37\,607\,912\,018 & 11 \\
+ 13 & 9\,316\,358\,251\,200 & 10\,752 & $-29$ & $+37$ & 346\,065\,536\,839 & 12 \\
+ 14 & 97\,821\,761\,637\,600 & 17\,280 & $-27$ & $+31$ & 3\,204\,941\,750\,802 & 12 \\
+ 15 & 866\,421\,317\,361\,600 & 26\,880 & $-11$ & $+37$ & 29\,844\,570\,422\,669 & 13 \\
+ 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & $-63$ & $+61$ & 279\,238\,341\,033\,925 & 13 \\
+ 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & $-3$ & $+3$ & 2\,623\,557\,157\,654\,233 & 14 \\
+ 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & 16 \\
\hline
\end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/probability.tex b/content/math/tables/probability.tex
index f265d10..29f92e1 100644
--- a/content/math/tables/probability.tex
+++ b/content/math/tables/probability.tex
@@ -1,19 +1,15 @@
-\begin{tabularx}{\linewidth}{|LICIR|}
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|LIR|}
\hline
- \multicolumn{3}{|c|}{
+ \multicolumn{2}{|c|}{
Wahrscheinlichkeitstheorie ($A,B$ Ereignisse und $X,Y$ Variablen)
} \\
\hline
- $\E(X + Y) = \E(X) + \E(Y)$ &
- $\E(\alpha X) = \alpha \E(X)$ &
- $X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$\\
-
- $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ &
- $A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$ &
- $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\
+ $\E(X + Y) = \E(X) + \E(Y)$ & $\Pr[A \vert B] = \frac{\Pr[A \land B]}{\Pr[B]}$ \\
+ $\E(\alpha X) = \alpha \E(X)$ & $\Pr[A \lor B] = \Pr[A] + \Pr[B] - \Pr[A \land B]$ \\
+ $X, Y$ unabh. $\Leftrightarrow \E(XY) = \E(X) \cdot \E(Y)$ & $A, B$ disj. $\Leftrightarrow \Pr[A \land B] = \Pr[A] \cdot \Pr[B]$\\
\hline
\end{tabularx}
-\vfill
\begin{tabularx}{\linewidth}{|Xlr|lrX|}
\hline
\multicolumn{6}{|c|}{\textsc{Bertrand}'s Ballot Theorem (Kandidaten $A$ und $B$, $k \in \mathbb{N}$)} \\
@@ -25,3 +21,4 @@
$\#A \geq \#B + k$ & $Num = \frac{a - k + 1 - b}{a - k + 1} \binom{a + b - k}{b}$ & \\
\hline
\end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/series.tex b/content/math/tables/series.tex
index 3042781..9618c2b 100644
--- a/content/math/tables/series.tex
+++ b/content/math/tables/series.tex
@@ -1,33 +1,33 @@
-\begin{tabularx}{\linewidth}{|XIXIXIX|}
- \hline
- \multicolumn{4}{|c|}{Reihen} \\
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|XIXIX|}
\hline
$\sum\limits_{i = 1}^n i = \frac{n(n+1)}{2}$ &
$\sum\limits_{i = 1}^n i^2 = \frac{n(n + 1)(2n + 1)}{6}$ &
- $\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ &
- $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\
+ $\sum\limits_{i = 1}^n i^3 = \frac{n^2 (n + 1)^2}{4}$ \\
\grayhline
- $\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \quad c \neq 1$ &
- $\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \quad \vert c \vert < 1$ &
- $\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \quad \vert c \vert < 1$ &
- $\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \quad \vert c \vert < 1$ \\
+ $\sum\limits_{i = 0}^n c^i = \frac{c^{n + 1} - 1}{c - 1} \hfill c \neq 1$ &
+ $\sum\limits_{i = 0}^\infty c^i = \frac{1}{1 - c} \hfill \vert c \vert < 1$ &
+ $\sum\limits_{i = 1}^\infty c^i = \frac{c}{1 - c} \hfill \vert c \vert < 1$ \\
\grayhline
-
+
\multicolumn{2}{|lI}{
$\sum\limits_{i = 0}^n ic^i = \frac{nc^{n + 2} - (n + 1)c^{n + 1} + c}{(c - 1)^2} \quad c \neq 1$
} &
- \multicolumn{2}{l|}{
+ $\sum\limits_{i = 0}^\infty ic^i = \frac{c}{(1 - c)^2} \hfill \vert c \vert < 1$ \\
+ \grayhline
+
+ \multicolumn{2}{|lI}{
$\sum\limits_{i = 1}^n iH_i = \frac{n(n + 1)}{2}H_n - \frac{n(n - 1)}{4}$
- } \\
+ } &
+ $H_n = \sum\limits_{i = 1}^n \frac{1}{i}$ \\
\grayhline
\multicolumn{2}{|lI}{
- $\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$
- } &
- \multicolumn{2}{l|}{
$\sum\limits_{i = 1}^n \binom{i}{m}H_i =
\binom{n + 1}{m + 1} \left(H_{n + 1} - \frac{1}{m + 1}\right)$
- } \\
+ } &
+ $\sum\limits_{i = 1}^n H_i = (n + 1)H_n - n$ \\
\hline
\end{tabularx}
+\end{expandtable}
diff --git a/content/math/tables/stuff.tex b/content/math/tables/stuff.tex
index 3cf8b4c..82f2d3f 100644
--- a/content/math/tables/stuff.tex
+++ b/content/math/tables/stuff.tex
@@ -1,6 +1,7 @@
-\begin{tabularx}{\linewidth}{|ll|}
+\begin{expandtable}
+\begin{tabularx}{\linewidth}{|Ll|}
\hline
- \multicolumn{2}{|C|}{Verschiedenes} \\
+ \multicolumn{2}{|c|}{Verschiedenes} \\
\hline
Türme von Hanoi, minimale Schirttzahl: &
$T_n = 2^n - 1$ \\
@@ -20,7 +21,7 @@
\#Wälder mit $k$ gewurzelten Bäumen &
$\frac{k}{n}\binom{n}{k}n^{n-k}$ \\
- \#Wälder mit $k$ gewurzelten Bäumen mit vorgegebenen Wurzelknoten&
+ \#Wälder mit $k$ gewurzelten~Bäumen mit vorgegebenen Wurzelknoten&
$\frac{k}{n}n^{n-k}$ \\
Derangements &
@@ -29,4 +30,4 @@
$\lim\limits_{n \to \infty} \frac{!n}{n!} = \frac{1}{e}$ \\
\hline
\end{tabularx}
-
+\end{expandtable}
diff --git a/content/math/transforms/seriesOperations.cpp b/content/math/transforms/seriesOperations.cpp
index 4743674..b405698 100644
--- a/content/math/transforms/seriesOperations.cpp
+++ b/content/math/transforms/seriesOperations.cpp
@@ -4,7 +4,7 @@ vector<ll> poly_inv(const vector<ll>& a, int n) {
vector<ll> a2 = a, q2 = q;
a2.resize(2*len), q2.resize(2*len);
ntt(q2);
- for (int j : {0, 1}) {
+ for (int _ : {0, 1}) {
ntt(a2);
for (int i = 0; i < 2*len; i++) a2[i] = a2[i]*q2[i] % mod;
ntt(a2, true);
@@ -24,10 +24,13 @@ vector<ll> poly_deriv(vector<ll> 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;
+ static vector<ll> inv = {0, 1};
+ for (static int i = 2; i <= sz(a); i++)
+ inv.push_back(mod - mod / i * inv[mod % i] % mod);
+
+ a.push_back(0);
+ for (int i = sz(a) - 1; i > 0; i--)
+ a[i] = a[i-1] * inv[i] % mod;
a[0] = 0;
return a;
}
@@ -35,8 +38,7 @@ vector<ll> poly_integr(vector<ll> 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;
+ return poly_integr(a);
}
vector<ll> poly_exp(vector<ll> a, int n) {
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 16:37:57 +0000