new linear recurrence kthTerm code

3 files changed, 33 insertions, 2 deletions

diff --git a/content/math/linearRecurrence.cpp b/content/math/linearRecurrence.cpp
new file mode 100644
index 0000000..c15c25c
--- /dev/null
+++ b/content/math/linearRecurrence.cpp
@@ -0,0 +1,30 @@
+// constexpr ll mod = 998244353;
+// 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(ll &x : c) x %= mod;
+// 	return c;
+// }
+
+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> 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];
+}
\ No newline at end of file
diff --git a/content/math/linearRecurence.cpp b/content/math/linearRecurrenceOld.cpp
index 2501e64..2501e64 100644
--- a/content/math/linearRecurence.cpp
+++ b/content/math/linearRecurrenceOld.cpp
diff --git a/content/math/math.tex b/content/math/math.tex
index dd88a5b..fb66110 100644
--- a/content/math/math.tex
+++ b/content/math/math.tex
@@ -136,9 +136,10 @@ 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}

-	\sourcecode{math/linearRecurence.cpp}

+	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}

 	\setlength\arraycolsep{3pt}