详细介绍：Leetcode 3700. Number of ZigZag Arrays II

• Leetcode 3700. Number of ZigZag Arrays II
  • 1. 解题思路
  • 2. 代码构建

• 题目链接：3700. Number of ZigZag Arrays II

1. 解题思路

这一题事实上就是上一题3699. Number of ZigZag Arrays I增加了就是的进阶版本，主要的变化就$n$的复杂度，$n$最大可以取到$10^9$，因此暴力的迭代显然就不现实了，但其核心的迭代公式依然还是上一题中分析的那样：
$$\{\begin{array}{rl}{u}_{n+1}^i& =\sum _{j=i+1}^r{d}_n^j\\ d_{n+1}^i& =\sum _{j=l}^{i-1}{u}_n^j\end{array}$$

这里，注意到，如果我们令$\vec{v}=\mathrm{concat}(\vec{u},\vec{d})$一个矩阵乘法：就是，那么事实上上述迭代过程可以写作
$${\vec{v}}_{n+1}=M\cdot {\vec{v}}_n$$

因此，不难推导：
$${\vec{v}}_n=M^{n-1}\cdot {\vec{v}}_1$$

此时，困难也就变成了如何快速地求矩阵$M$的$n-1$了，这个就变成了一个常规的二分处理的算法了。

当然，既然这里涉及到了矩阵乘法，因此，我们自然而然就可以启用numpy来加速一下运算了，这里就不过多展开了。

2. 代码实现

给出python代码实现如下：

import numpy as np
MOD = 10**9 + 7
class Solution:
def zigZagArrays(self, n: int, l: int, r: int) -> int:
d = r-l+1
vec = [1 for _ in range(d-1)] + [0] + [0] + [1 for _ in range(d-1)]
vec = np.array(vec, dtype=object)
M = [[0 for _ in range(2*d)] for _ in range(2*d)]
for i in range(d):
for j in range(i+1, d):
M[i][d+j] = 1
for j in range(i):
M[i+d][j] = 1
M = np.array(M, dtype=object)
def pow_mul(M, vec, n):
res = vec
while n:
if n % 2 == 1:
res = (M @ res) % MOD
M = (M @ M) % MOD
n = n // 2
return res
res = pow_mul(M, vec, n-1)
return sum(res) % MOD

提交代码评测得到：耗时4045ms，占用内存31.78MB。