leetcode

commit 82839d5575c0ebe2897a1cd219067cbb3f701924
parent d05edef340c99714a5696b9eb58df1775b73a782
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed, 24 Jun 2026 09:53:19 -0600

3700. number of zigzag arrays 2

Diffstat:
A
num_zigzag_arrays2.c
 | 
84
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
num_zigzag_arrays2.py
 | 
58
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 142 insertions(+), 0 deletions(-)
diff --git a/num_zigzag_arrays2.c b/num_zigzag_arrays2.c
@@ -0,0 +1,84 @@
+// 3700. Number of ZigZag Arrays II
+#include "leetcode.h"
+
+/*
+ * you are given three integers. a zigzag array of length 'n' is defined as
+ * follows: each element lies in the range '[l, r]', no two adjacent elements
+ * are equal, and no three consecutive elements form a strictly increasing or
+ * decreasing sequence. return the total number of valid zigzag arrays. since
+ * the answer may be large, return it modulo 10^9+7.
+ */
+
+static int mod = 1e9 + 7;
+
+long long **matrix_init(int n) {
+  long long **res = (long long **)malloc(n * sizeof(long long *));
+  for (int i = 0; i < n; i++)
+    res[i] = (long long *)calloc(n, sizeof(long long));
+  return res;
+}
+
+void matrix_free(long long **matrix, int n) {
+  for (int i = 0; i < n; i++)
+    free(matrix[i]);
+  free(matrix);
+}
+
+long long **matrix_multiply(long long **a, long long **b, int n) {
+  long long **res = matrix_init(n);
+  for (int row = 0; row < n; row++)
+    for (int mid = 0; mid < n; mid++) {
+      if (!a[row][mid])
+        continue;
+      for (int col = 0; col < n; col++)
+        res[row][col] = (res[row][col] + a[row][mid] * b[mid][col]) % mod;
+    }
+  return res;
+}
+
+long long **matrix_power(long long **matrix, int power, int n) {
+  long long **res = matrix_init(n);
+  for (int row = 0; row < n; row++)
+    res[row][row] = 1;
+  while (power > 0) {
+    if (power & 1) {
+      long long **tmp = matrix_multiply(res, matrix, n);
+      matrix_free(res, n);
+      res = tmp;
+    }
+    long long **tmp = matrix_multiply(matrix, matrix, n);
+    matrix_free(matrix, n);
+    matrix = tmp;
+    power >>= 1;
+  }
+  matrix_free(matrix, n);
+  return res;
+}
+
+int zigZagArrays(int n, int l, int r) {
+  int val_cnt = r - l + 1;
+  long long *dp = (long long *)malloc(val_cnt * sizeof(long long));
+  for (int i = 0; i < val_cnt; i++)
+    dp[i] = i;
+  long long **trans = matrix_init(val_cnt);
+  for (int row = 1; row < val_cnt; row++)
+    for (int col = val_cnt - row; col < val_cnt; col++)
+      trans[row][col] = 1;
+  long long **pow_trans = matrix_power(trans, n - 2, val_cnt);
+  long long ans = 0;
+  for (int row = 0; row < val_cnt; row++)
+    for (int col = 0; col < val_cnt; col++)
+      ans = (ans + pow_trans[row][col] * dp[col]) % mod;
+  free(dp);
+  matrix_free(pow_trans, val_cnt);
+  return ans * 2 % mod;
+}
+
+int main() {
+  int r1 = zigZagArrays(3, 4, 5);
+  int r2 = zigZagArrays(3, 1, 3);
+  printf("%d\n", r1);
+  assert(r1 == 2);
+  printf("%d\n", r2);
+  assert(r2 == 10);
+}
diff --git a/num_zigzag_arrays2.py b/num_zigzag_arrays2.py
@@ -0,0 +1,58 @@
+# 3700. Number of ZigZag Arrays II
+
+"""
+you are given three integers. a zigzag array of length 'n' is defined as
+follows: each element lies in the range '[l, r]', no two adjacent elements
+are equal, and no three consecutive elements form a strictly increasing or
+decreasing sequence. return the total number of valid zigzag arrays. since
+the ans may be large, return it modulo 10^9+7.
+"""
+
+
+class Solution:
+    mod = 10**9 + 7
+
+    def matrix_multiply(self, a, b):
+        n = len(a)
+        res = [[0] * n for _ in range(n)]
+        for row in range(n):
+            for mid in range(n):
+                if a[row][mid] == 0:
+                    continue
+
+                for col in range(n):
+                    res[row][col] = (
+                        res[row][col] + a[row][mid] * b[mid][col]
+                    ) % self.mod
+
+        return res
+
+    def matrix_power(self, matrix, power):
+        n = len(matrix)
+        res = [[1 if row == col else 0 for col in range(n)] for row in range(n)]
+        while power:
+            if power & 1:
+                res = self.matrix_multiply(res, matrix)
+            matrix = self.matrix_multiply(matrix, matrix)
+            power >>= 1
+        return res
+
+    def zigZagArrays(self, n: int, l: int, r: int) -> int:
+        val_cnt = r - l + 1
+        dp = list(range(val_cnt))
+        trans = [[0] * val_cnt for _ in range(val_cnt)]
+        for row in range(1, val_cnt):
+            for col in range(val_cnt - row, val_cnt):
+                trans[row][col] = 1
+        pow_trans = self.matrix_power(trans, n - 2)
+        ans = 0
+        for row in range(val_cnt):
+            for col in range(val_cnt):
+                ans = (ans + pow_trans[row][col] * dp[col]) % self.mod
+        return (ans * 2) % self.mod
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.zigZagArrays(n=3, l=4, r=5))
+    print(obj.zigZagArrays(n=3, l=1, r=3))