diff options
| -rw-r--r-- | math/inversions.cpp | 27 | ||||
| -rw-r--r-- | math/math.tex | 3 | ||||
| -rw-r--r-- | math/multInv.cpp | 2 | ||||
| -rw-r--r-- | math/primeSieve.cpp | 4 | ||||
| -rw-r--r-- | tcr.pdf | bin | 310675 -> 312533 bytes |
5 files changed, 34 insertions, 2 deletions
diff --git a/math/inversions.cpp b/math/inversions.cpp new file mode 100644 index 0000000..0720407 --- /dev/null +++ b/math/inversions.cpp @@ -0,0 +1,27 @@ +// Laufzeit: O(n*log(n)) +ll merge(vector<ll> &v, vector<ll> &left, vector<ll> &right) { + int a = 0, b = 0, i = 0; + ll inv = 0; + while (a < (int)left.size() && b < (int)right.size()) { + if (left[a] < right[b]) v[i++] = left[a++]; + else { + inv += left.size() - a; + v[i++] = right[b++]; + } + } + while (a < (int)left.size()) v[i++] = left[a++]; + while (b < (int)right.size()) v[i++] = right[b++]; + return inv; +} + +ll mergeSort(vector<ll> &v) { // Sortiert v und gibt Inversionszahl zurück. + int n = v.size(); + vector<ll> left(n / 2), right((n + 1) / 2); + for (int i = 0; i < n / 2; i++) left[i] = v[i]; + for (int i = n / 2; i < n; i++) right[i - n / 2] = v[i]; + + ll result = 0; + if (left.size() > 1) result += mergeSort(left); + if (right.size() > 1) result += mergeSort(right); + return result + merge(v, left, right); +} diff --git a/math/math.tex b/math/math.tex index c02d352..1a4a684 100644 --- a/math/math.tex +++ b/math/math.tex @@ -120,6 +120,9 @@ Multipliziert Polynome $A$ und $B$. \subsection{Longest Increasing Subsequence} \lstinputlisting{math/longestIncreasingSubsequence.cpp} +\subsection{Inversionszahl und Mergesort} +\lstinputlisting{math/inversions.cpp} + \subsection{Satz von \textsc{Sprague-Grundy}} Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu: \[ diff --git a/math/multInv.cpp b/math/multInv.cpp index 2aedcd6..4e388b8 100644 --- a/math/multInv.cpp +++ b/math/multInv.cpp @@ -2,6 +2,6 @@ ll multInv(ll n, ll p) { ll x, y; extendedEuclid(n, p, x, y); // Implementierung von oben. - x += ((x / p) + 1) * p; + x = ((x % p) + p) % p; return x % p; } diff --git a/math/primeSieve.cpp b/math/primeSieve.cpp index 7e8b288..286aa1d 100644 --- a/math/primeSieve.cpp +++ b/math/primeSieve.cpp @@ -1,4 +1,6 @@ // Laufzeit: O(n * log log n) +// Kann erweitert werden: Für jede Zahl den kleinsten Primfaktor. +// Dabei vorsicht: Nicht kleinere Faktoren überschreiben. #define N 100000000 // Bis 10^8 in unter 64MB Speicher. bitset<N / 2> isNotPrime; @@ -13,7 +15,7 @@ inline int primeSieve() { // Rückgabe: Anzahl der Primzahlen < N. int counter = 1; // Die 2, die sonst vergessen würde. for (int i = 3; i < N; i += 2) { if (!isNotPrime[i / 2]) { - for (int j = 3 * i; j < N; j+= 2 * i) isNotPrime[j / 2] = 1; + for (int j = i * i; j < N; j+= 2 * i) isNotPrime[j / 2] = 1; counter++; }} return counter; Binary files differ |