1 files changed, 14 insertions, 0 deletions
diff --git a/content/math/matrixPower.cpp b/content/math/matrixPower.cpp
new file mode 100644
index 0000000..d981e6e
--- /dev/null
+++ b/content/math/matrixPower.cpp
@@ -0,0 +1,14 @@
+vector<mat> pows;
+
+void precalc(mat m) {
+	pows = {mat(sz(m.m), 1), m};
+	for (int i = 1; i < 60; i++) pows.push_back(pows[i] * pows[i]);
+}
+
+auto calc(ll b, vector<ll> v) {
+	for (ll i = 1; b > 0; i++) {
+		if (b & 1) v = pows[i] * v;
+		b /= 2;
+	}
+	return v;
+}