Skip to content

3916. Number of ZigZag Arrays III πŸ”’

DifficultyHard

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.

 

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 <= 200
  • 1 <= l < r <= 10​​​​​​​9

Solutions

Solution 1

Thinking

The value interval can be as long as \(10^9\) while \(n\le 200\), so we cannot enumerate concrete numbers. Zigzag constraints only care about the rise/fall pattern of three consecutive entries, i.e. relative order.

After treating \([l,r]\) as a total order of length \(m=r-l+1\), a state is β€œprevious value plus current direction”. \(m\) may still be huge, so transitions over values must be written with prefix sums or matrices.

This directory has no implemented solution yet; the walkthrough stops at that observation that DP must run on relative order rather than raw values.

1


1


1


1

Comments