题目分析

本题实际上要求的是满足以下条件的数组数量：

  1. 长度为给定值$n$；
  2. 每一个值都在限定范围$[l,r]$内；
  3. 相邻两个位置的关系从左到右依次增减交替变化。

基本思路

动态规划思路

由于本题要保证的只是数字的大小关系，并没有强制要求按照区间$[l,r]$进行计算，因此为了简便计算，可以将$l$和$r$都减少$l$，使区间变为$[0,r-l]$，这和原有情况是等价的。

本题要求最终的数组长度为$n$，如果此时确定第$n$个数字是$x$，并且确定最后两个数字呈上升趋势，那么就可以确定第$n-1$个数字的取值范围，这样，问题其实变成了一个相似但规模更小的问题。因此可以使用动态规划来解决该问题。仿照上面的分析，可以定义两个动态规划数组如下：

  1. $dp0[i][j]$表示数组长度为$i$且第$i$个数字为$j$时，最后两个数字呈上升趋势的情况下，数组的总数量；
  2. $dp1[i][j]$表示数组长度为$i$且第$i$个数字为$j$时，最后两个数字呈下降趋势的情况下，数组的总数量。

这样，答案就应该是$sum(dp0[n])+sum(dp1[n])$。

那么对于$dp0[i][j]$，由于最后两个数字呈上升趋势，因此可以确定第$i-1$个数字的取值范围为$[l,j-1]$，并且第$i-2$和第$i-1$个数字必须呈下降趋势，故可得递推公式如下：

$$ dp0[i][j] = \sum_{k=l}^{j-1}dp1[i-1][k] $$

类似的，对于$dp1[i][j]$，也可以得到递推公式如下：

$$ dp1[i][j] = \sum_{k=j+1}^{r}dp0[i-1][k] $$

根据上面两个公式，即可写出动态规划代码。观察到在递推关系式中用到了区间求和，因此可以用前缀和来优化，当加上前缀和优化时，本题目的第$I$题即可通过了。

矩阵乘法和快速幂优化

观察上面两个递推式子，不难发现，如果将$dp0[i]$和$dp1[i]$合并成一个长度为$2 \times (r-l+1)$的数组$dp[i]$，那么每一个$dp[i]$实际上都可以用同样一个公式从$dp[i-1]$中计算得来，而如果将$dp[i]$看作一个维度是$2 \times (r-l+1)$的空间中的一个坐标，那么上面说的这个递推公式其实可以看作一个坐标变换矩阵，每次只需用同样的矩阵乘以原来的坐标，即可得到新的坐标。 （注意，两个数组经过上述合并后，$dp0$中原有的索引不变，但$dp1$中原有的索引会增加$r-l+1$。为叙述方便，定义$k = r-l+1$）

举个例子，如果$k=2$，也就意味着数组中的每个位置上都只有两个数字可以选，那么根据之前的递推公式可以得到：

  1. $dp0[i][0] = 0$;
  2. $dp0[i][1]=dp1[i-1][0]$;
  3. $dp1[i][0]=dp0[i-1][1]$;
  4. $dp1[i][1] = 0$.

而如果将$dp0[i][x]$换成$dp[i][x]$，并将$dp1[i][x]$换成$dp[i][x+k]$，即可得到以下递推式：

  1. $dp[i][0] = 0$;
  2. $dp[i][1] = dp[i-1][2]$;
  3. $dp[i][2] = dp[i-1][1]$;
  4. $dp[i][3] = 0$;

因此可以整理出从$dp[i-1]$转成$dp[i]$所需要进行的坐标变换矩阵如下：

$$ \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} $$

总结规律，可以发现，对于任意一个$k$值，对应的坐标变换矩阵都可以按照下面方式列写：

  1. 第$i$行$(2 \leq i\leq k)$：$\underbrace{0 \dots \dots \dots 0}_{k} \space \space \space \underbrace{1 \dots 1}_{i-1} \space \space \space \underbrace{0 \dots 0}_{k-i+1}$
  2. 第$i$行$(k+1 \leq i \leq 2k)$：$\underbrace{0 \dots 0}_{k-i+1} \space \space \space \underbrace{1 \dots 1}_{i-1} \space \space \space \underbrace{0 \dots \dots \dots 0}_{k}$

记上面的坐标变换矩阵为$M$，由于$dp[n-1]$是由$dp[0]$进行$n-1$次坐标变化得来的，因此有以下等式：

$$ dp[n-1] = \underbrace{M\cdot M \dots M \cdot M}_{n-1} \cdot dp[0]=M^{n-1}\cdot dp[0] $$

故如果求得了坐标变换矩阵$M$，即可根据上述公式求得最终的$dp[n-1]$，同时注意到公式中存在幂运算，因此可以用快速幂的方式进行优化，这里就不再多说了。

唯一需要注意的就是，$dp[0]$数组的初始值应当全部设置为1。

复杂度

时间复杂度：$O(k^3\cdot logn)$，其中$k=r-l+1$. 空间复杂度：$O(k^2)$，其中$k=r-l+1$.

代码

modNum = 1_000_000_007

def matrixMultiply(a, b):
    n, m = len(a), len(b[0])
    c = [[0]*m for _ in range(n)]
    for i in range(n):
        for k in range(len(a[0])):
            if a[i][k] == 0:
                continue
            for j in range(m):
                c[i][j] = (c[i][j]+a[i][k]*b[k][j])%modNum
    return c

def quickPow(mat, x, dp):
    res = dp
    while x:
        if x&1:
            res = matrixMultiply(mat, res)
        mat = matrixMultiply(mat, mat)
        x >>= 1
    return res

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        k = r-l+1
        mat = [[0]*(2*k) for _ in range(2*k)]
        for i in range(k):
            for j in range(i):
                mat[i][j+k] = 1
            for j in range(i+1, k):
                mat[i+k][j] = 1
        
        dp = [[1] for _ in range(2*k)]
        resMat = quickPow(mat, n-1, dp)

        res = 0
        for row in resMat:
            res = (res+row[0])%modNum
        return res