Welcome to Subscribe On Youtube

3700. Number of ZigZag Arrays II

Description

You are given three integers n, l, and r.

A ZigZag array of length n is defined as follows:

• Each element lies in the range [l, r].
• No two adjacent elements are equal.
• No three consecutive elements form a strictly increasing or strictly decreasing sequence.

Return the total number of valid ZigZag arrays.

Since the answer may be large, return it modulo 109 + 7.

A sequence is said to be strictly increasing if each element is strictly greater than its previous one (if exists).

A sequence is said to be strictly decreasing if each element is strictly smaller than its previous one (if exists).

 

Example 1:

Input: n = 3, l = 4, r = 5

Output: 2

Explanation:

There are only 2 valid ZigZag arrays of length n = 3 using values in the range [4, 5]:

• [4, 5, 4]
• [5, 4, 5]

Example 2:

Input: n = 3, l = 1, r = 3

Output: 10

Explanation:

​​​​​​​There are 10 valid ZigZag arrays of length n = 3 using values in the range [1, 3]:

• [1, 2, 1], [1, 3, 1], [1, 3, 2]
• [2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2]
• [3, 1, 2], [3, 1, 3], [3, 2, 3]

All arrays meet the ZigZag conditions.

 

Constraints:

• 3 <= n <= 109
• 1 <= l < r <= 75​​​​​​​

Solutions

Solution 1

• Java

• class Solution {
      private static final long MOD = 1_000_000_007L;
  
      public int zigZagArrays(int n, int l, int r) {
          int m = r - l + 1;
          int size = 2 * m;
  
          long[][] trans = new long[size][size];
          for (int x = 0; x < m; x++) {
              for (int y = 0; y < x; y++) {
                  trans[y][m + x] = 1;
              }
          }
  
          // down[x] -> up[y] where y > x
          for (int x = 0; x < m; x++) {
              for (int y = x + 1; y < m; y++) {
                  trans[m + y][x] = 1;
              }
          }
  
          long[][] power = matrixPow(trans, n - 1);
  
          long[] init = new long[size];
          for (int i = 0; i < m; i++) {
              init[i] = 1;
              init[m + i] = 1;
          }
  
          long[] result = multiply(power, init);
  
          long ans = 0;
          for (long v : result) {
              ans = (ans + v) % MOD;
          }
  
          return (int) ans;
      }
  
      private long[] multiply(long[][] mat, long[] vec) {
          int n = mat.length;
          long[] res = new long[n];
  
          for (int i = 0; i < n; i++) {
              long sum = 0;
              for (int j = 0; j < n; j++) {
                  sum = (sum + mat[i][j] * vec[j]) % MOD;
              }
              res[i] = sum;
          }
  
          return res;
      }
  
      private long[][] matrixPow(long[][] mat, long exp) {
          int n = mat.length;
  
          long[][] res = new long[n][n];
          for (int i = 0; i < n; i++) {
              res[i][i] = 1;
          }
  
          while (exp > 0) {
              if ((exp & 1) == 1) {
                  res = multiply(res, mat);
              }
  
              mat = multiply(mat, mat);
              exp >>= 1;
          }
  
          return res;
      }
  
      private long[][] multiply(long[][] a, long[][] b) {
          int n = a.length;
          long[][] res = new long[n][n];
  
          for (int i = 0; i < n; i++) {
              for (int k = 0; k < n; k++) {
                  if (a[i][k] == 0) continue;
  
                  long aik = a[i][k];
  
                  for (int j = 0; j < n; j++) {
                      if (b[k][j] == 0) continue;
  
                      res[i][j] = (res[i][j] + aik * b[k][j]) % MOD;
                  }
              }
          }
  
          return res;
      }
  }
  
  

All Problems

All Solutions