From 36ba8589fa0154d73354bd8e0101213f2d5f9ba4 Mon Sep 17 00:00:00 2001 From: Yidi Date: Fri, 22 Mar 2024 12:21:56 +0100 Subject: reorder to improve spacing --- tcr.pdf | Bin 667178 -> 664992 bytes 1 file changed, 0 insertions(+), 0 deletions(-) (limited to 'tcr.pdf') diff --git a/tcr.pdf b/tcr.pdf index e7330c0..6342868 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 4680159f439b3b9651321e2dc9083a51fe6ce954 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Tue, 4 Jun 2024 15:56:33 +0200 Subject: fix havel hakimi --- graph/havelHakimi.cpp | 4 +++- graph/scc.cpp | 15 ++++++--------- tcr.pdf | Bin 664992 -> 665092 bytes 3 files changed, 9 insertions(+), 10 deletions(-) (limited to 'tcr.pdf') diff --git a/graph/havelHakimi.cpp b/graph/havelHakimi.cpp index 6246fe0..cbd6991 100644 --- a/graph/havelHakimi.cpp +++ b/graph/havelHakimi.cpp @@ -1,6 +1,8 @@ vector> havelHakimi(const vector& deg) { priority_queue> pq; - for (int i = 0; i < sz(deg); i++) pq.push({deg[i], i}); + for (int i = 0; i < sz(deg); i++) { + if (deg[i] > 0) pq.push({deg[i], i}); + } vector> adj; while (!pq.empty()) { auto [degV, v] = pq.top(); pq.pop(); diff --git a/graph/scc.cpp b/graph/scc.cpp index 5aa7cf2..ac9a40b 100644 --- a/graph/scc.cpp +++ b/graph/scc.cpp @@ -1,5 +1,5 @@ vector> adj, sccs; -int counter, sccCounter; +int counter; vector inStack; vector low, idx, s; //idx enthält Index der SCC pro Knoten. @@ -14,14 +14,11 @@ void visit(int v) { if (old == low[v]) { sccs.push_back({}); - int u; - do { + for (int u = -1; u != v;) { u = s.back(); s.pop_back(); inStack[u] = false; - idx[u] = sccCounter; - sccs[sccCounter].push_back(u); - } while (u != v); - sccCounter++; -}} + idx[u] = sz(sccs) - 1; + sccs.back().push_back(u); +}}} void scc() { inStack.assign(sz(adj), false); @@ -29,7 +26,7 @@ void scc() { idx.assign(sz(adj), -1); sccs.clear(); - counter = sccCounter = 0; + counter = 0; for (int i = 0; i < sz(adj); i++) { if (low[i] < 0) visit(i); }} diff --git a/tcr.pdf b/tcr.pdf index 6342868..c22d0d5 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3 From 500ac1e618410ac453fa4fe83e2348cad8c2418f Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 22 Jun 2024 21:12:39 +0200 Subject: fix --- math/binomial0.cpp | 2 +- math/math.tex | 1 + math/tables/composite.tex | 42 +++++++++++++++++++++--------------------- tcr.pdf | Bin 665092 -> 664604 bytes 4 files changed, 23 insertions(+), 22 deletions(-) (limited to 'tcr.pdf') diff --git a/math/binomial0.cpp b/math/binomial0.cpp index d9af917..896a0f1 100644 --- a/math/binomial0.cpp +++ b/math/binomial0.cpp @@ -10,5 +10,5 @@ void precalc() { 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; + return (inv[n] * inv[n-k] % mod) * fac[k] % mod; } diff --git a/math/math.tex b/math/math.tex index 8a30b86..f9a5ea5 100644 --- a/math/math.tex +++ b/math/math.tex @@ -409,6 +409,7 @@ so gilt %\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} diff --git a/math/tables/composite.tex b/math/tables/composite.tex index b4c8294..1d06a62 100644 --- a/math/tables/composite.tex +++ b/math/tables/composite.tex @@ -1,26 +1,26 @@ -\begin{tabularx}{\linewidth}{|r|r|r|CICICICICICICICICICICIC|} +\begin{tabularx}{\linewidth}{|r||r|r||r|r|r||C|} \hline - \multicolumn{15}{|c|}{Highly Composite Numbers} \\ + \multicolumn{7}{|c|}{Important Numbers} \\ \hline - $10^x$ & Zahl & Teiler & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 \\ + $10^x$ & Highly Composite & \# Divs & $<$ Prime & $>$ Prime & \# Primes & \\ \hline - 1 & 6 & 4 & 1 & 1 & & & & & & & & & & \\ - 2 & 60 & 12 & 2 & 1 & 1 & & & & & & & & & \\ - 3 & 840 & 32 & 3 & 1 & 1 & 1 & & & & & & & &\\ - 4 & 7560 & 64 & 3 & 3 & 1 & 1 & & & & & & & & \\ - 5 & 83160 & 128 & 3 & 3 & 1 & 1 & 1 & & & & & & & \\ - 6 & 720720 & 240 & 4 & 2 & 1 & 1 & 1 & 1 & & & & & & \\ - 7 & 8648640 & 448 & 6 & 3 & 1 & 1 & 1 & 1 & & & & & & \\ - 8 & 73513440 & 768 & 5 & 3 & 1 & 1 & 1 & 1 & 1 & & & & & \\ - 9 & 735134400 & 1344 & 6 & 3 & 2 & 1 & 1 & 1 & 1 & & & & & \\ - 10 & 6983776800 & 2304 & 5 & 3 & 2 & 1 & 1 & 1 & 1 & 1 & & & & \\ - 11 & 97772875200 & 4032 & 6 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & & & & \\ - 12 & 963761198400 & 6720 & 6 & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & & & \\ - 13 & 9316358251200 & 10752 & 6 & 3 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & & \\ - 14 & 97821761637600 & 17280 & 5 & 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & & \\ - 15 & 866421317361600 & 26880 & 6 & 4 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\ - 16 & 8086598962041600 & 41472 & 8 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \\ - 17 & 74801040398884800 & 64512 & 6 & 3 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ - 18 & 897612484786617600 & 103680 & 8 & 4 & 2 & 2 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ + 1 & 6 & 4 & $-3$ & $+1$ & 4 & \\ + 2 & 60 & 12 & $-3$ & $+1$ & 25 & \\ + 3 & 840 & 32 & $-3$ & $+9$ & 168 & \\ + 4 & 7\,560 & 64 & $-27$ & $+7$ & 1\,229 & \\ + 5 & 83\,160 & 128 & $-9$ & $+3$ & 9\,592 & \\ + 6 & 720\,720 & 240 & $-17$ & $+3$ & 78\,498 & \\ + 7 & 8\,648\,640 & 448 & $-9$ & $+19$ & 664\,579 & \\ + 8 & 73\,513\,440 & 768 & $-11$ & $+7$ & 5\,761\,455 & \\ + 9 & 735\,134\,400 & 1\,344 & $-63$ & $+7$ & 50\,847\,534 & \\ + 10 & 6\,983\,776\,800 & 2\,304 & $-33$ & $+19$ & 455\,052\,511 & \\ + 11 & 97\,772\,875\,200 & 4\,032 & $-23$ & $+3$ & 4\,118\,054\,813 & \\ + 12 & 963\,761\,198\,400 & 6\,720 & $-11$ & $+39$ & 37\,607\,912\,018 & \\ + 13 & 9\,316\,358\,251\,200 & 10\,752 & $-29$ & $+37$ & 346\,065\,536\,839 & \\ + 14 & 97\,821\,761\,637\,600 & 17\,280 & $-27$ & $+31$ & 3\,204\,941\,750\,802 & \\ + 15 & 866\,421\,317\,361\,600 & 26\,880 & $-11$ & $+37$ & 29\,844\,570\,422\,669 & \\ + 16 & 8\,086\,598\,962\,041\,600 & 41\,472 & $-63$ & $+61$ & 279\,238\,341\,033\,925 & \\ + 17 & 74\,801\,040\,398\,884\,800 & 64\,512 & $-3$ & $+3$ & 2\,623\,557\,157\,654\,233 & \\ + 18 & 897\,612\,484\,786\,617\,600 & 103\,680 & $-11$ & $+3$ & 24\,739\,954\,287\,740\,860 & \\ \hline \end{tabularx} diff --git a/tcr.pdf b/tcr.pdf index c22d0d5..63ebc4a 100644 Binary files a/tcr.pdf and b/tcr.pdf differ -- cgit v1.2.3