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 <= 1091 <= l < r <= 75
Solutions
A more complicated version of yesterday's problem. Way too much for breakfast.
/**
* @param {number} n
* @param {number} l
* @param {number} r
* @return {number}
*/
var zigZagArrays = function (n, l, r) {
const MOD = 1000000007n;
const k = r - l + 1;
if (k <= 0) return 0;
let m = Array.from({ length: k }, (_, i) =>
Array.from({ length: k }, (_, j) => (i + j + 1 < k ? 1n : 0n))
);
let res = Array(k).fill(1n);
n -= 1;
function matMul(a, b) {
const sz = a.length;
const c = Array.from({ length: sz }, () => Array(sz).fill(0n));
for (let i = 0; i < sz; i++) {
for (let k = 0; k < sz; k++) {
if (a[i][k] === 0n) continue;
for (let j = 0; j < sz; j++) {
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
}
}
}
return c;
}
function vecMatMul(v, mat) {
const sz = v.length;
const res = Array(sz).fill(0n);
for (let j = 0; j < sz; j++) {
for (let i = 0; i < sz; i++) {
res[j] = (res[j] + v[i] * mat[i][j]) % MOD;
}
}
return res;
}
while (n > 0) {
if (n & 1) res = vecMatMul(res, m);
m = matMul(m, m);
n >>= 1;
}
const total = res.reduce((a, b) => (a + b) % MOD, 0n);
return Number((total * 2n) % MOD);
};