new linear recurrence kthTerm code

1 files changed, 30 insertions, 0 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