diff options
Diffstat (limited to 'content')
| -rw-r--r-- | content/geometry/hpi.cpp | 16 | ||||
| -rw-r--r-- | content/math/linearRecurrence.cpp | 14 | ||||
| -rw-r--r-- | content/math/math.tex | 7 | ||||
| -rw-r--r-- | content/math/recover.cpp (renamed from content/other/recover.cpp) | 0 | ||||
| -rw-r--r-- | content/other/other.tex | 18 |
5 files changed, 27 insertions, 28 deletions
diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp index c58a6e7..f3dc08d 100644 --- a/content/geometry/hpi.cpp +++ b/content/geometry/hpi.cpp @@ -27,22 +27,22 @@ struct hp { if (ort == 0) return cross(from, to, a.from) < 0; return cross(b.dir(), a.dir()) * ort > 0; } - ll y = cross(a.dir(), b.dir()); - ll z = cross(b.from - a.from, b.dir()); - ptl i = mul(y, a.from) + mul(z, a.dir()); //intersect a and b - // check if i is outside/right of x - return imag(conj(mul(sgn(y),dir()))*(i-mul(y,from))) < 0; + ll x = cross(a.dir(), b.dir()); + ll y = cross(b.from - a.from, b.dir()); + ptl i = mul(x, a.from) + mul(y, a.dir()); //intersect a and b + // check if i is outside/right of this + return imag(conj(mul(sgn(x),dir()))*(i-mul(x,from))) < 0; } }; constexpr ll lim = 2e9+7; deque<hp> intersect(vector<hp> hps) { - hps.push_back(hp(pt{lim+1,-1})); - hps.push_back(hp(pt{lim+1,1})); + hps.push_back(hp(pt{lim + 1, -1})); + hps.push_back(hp(pt{lim + 1, 1})); sort(all(hps)); - deque<hp> dq = {hp(pt{-lim, 1})}; + deque<hp> dq = {hp(pt{-lim - 1, 1})}; for (auto x : hps) { while (sz(dq) > 1 && x.check(dq.end()[-1], dq.end()[-2])) dq.pop_back(); diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp index c15c25c..ab86f71 100644 --- a/content/math/linearRecurrence.cpp +++ b/content/math/linearRecurrence.cpp @@ -10,21 +10,21 @@ // return c; // } -ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k){ +ll kthTerm(const vector<ll>& f, const vector<ll>& c, ll k) { int n = sz(c); - vector<ll> q(n+1, 1); - for(int i = 1; i <= n; i++) q[i] = (mod-c[i-1])%mod; + 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{ + do { vector<ll> q2 = q; - for(int i = 1; i <= n; i += 2) q2[i] = (mod - q2[i]) % mod; + 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++){ + 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); + } while (k /= 2); return p[0]; }
\ No newline at end of file diff --git a/content/math/math.tex b/content/math/math.tex index fb66110..4ac6c9e 100644 --- a/content/math/math.tex +++ b/content/math/math.tex @@ -544,6 +544,11 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text \subsection{Wichtige Zahlen}
\input{math/tables/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}
@@ -552,10 +557,10 @@ Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \text \method{pi}{zählt Primzahlen $\leq n$ ($n < N^2$)}{n^{2/3}}
\end{methods}
\sourcecode{math/piLehmer.cpp}
-}
\subsection{Primzahlzählfunktion $\boldsymbol{\pi}$}
\sourcecode{math/piLegendre.cpp}
+}
\begin{algorithm}[optional]{Big Integers}
\sourcecode{math/bigint.cpp}
diff --git a/content/other/recover.cpp b/content/math/recover.cpp index 1a593f0..1a593f0 100644 --- a/content/other/recover.cpp +++ b/content/math/recover.cpp diff --git a/content/other/other.tex b/content/other/other.tex index 368d0b3..191a6da 100644 --- a/content/other/other.tex +++ b/content/other/other.tex @@ -72,6 +72,12 @@ \sourcecode{other/sos.cpp}
\end{algorithm}
+\begin{algorithm}{Fast Subset Sum}
+ \method{fastSubsetSum}{findet maximale subset $\mathit{sum}\leq t$}{n \cdot A}
+ Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
+ \sourcecode{other/fastSubsetSum.cpp}
+\end{algorithm}
+
\begin{algorithm}{Parallel Binary Search}
\sourcecode{other/pbs.cpp}
\end{algorithm}
@@ -95,18 +101,6 @@ \textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $\boldsymbol{1, \ldots, n}$ nummeriert sind, im zweiten Fall von $\boldsymbol{0, \ldots, n-1}$!}
\end{algorithm}
-\vfill\null\columnbreak
-
-\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{other/recover.cpp}
-
-\subsection{Fast Subset Sum}
-\method{fastSubsetSum}{findet maximale subset sum $\leq t$}{n \cdot A}
-Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
-\sourcecode{other/fastSubsetSum.cpp}
-
\begin{algorithm}[optional]{Zeileneingabe}
\sourcecode{other/split.cpp}
\end{algorithm}
|