1 files changed, 16 insertions, 0 deletions
diff --git a/math/matrixPower.cpp b/math/matrixPower.cpp
new file mode 100644
index 0000000..d3c1b63
--- /dev/null
+++ b/math/matrixPower.cpp
@@ -0,0 +1,16 @@
+vector<mat> pows;
+
+void precalc(mat m) {
+	pows = {mat(1), m};
+	for (int i = 1; i < 60; i++) pows.push_back(pows[i] * pows[i]);
+}
+
+ll calc(int x, int y, ll b) {
+	vector<ll> v(pows[0].m.size());
+	v[x] = 1;
+	for (ll i = 1; b > 0; i++) {
+		if (b & 1) v = pows[i] * v;
+		b /= 2;
+	}
+	return v[y];
+}
+\ No newline at end of file