rustimpl Solution {pub fn zig_zag_arrays(n: i32, l: i32, r: i32) - i32 {const MOD: i64 1_000_000_007;let m (r - l 1) as usize; // 值域大小if n 1 {return m as i32;}// 初始长度为1每个值都可作为起点up和down各为1let mut up vec![1i64; m];let mut down vec![1i64; m];// 重复添加 n-1 个元素for _ in 1..n {// 前缀和用于计算 new_uplet mut prefix_down vec![0i64; m 1];for i in 0..m {prefix_down[i 1] (prefix_down[i] down[i]) % MOD;}// 后缀和用于计算 new_downlet mut suffix_up vec![0i64; m 1];for i in (0..m).rev() {suffix_up[i] (suffix_up[i 1] up[i]) % MOD;}let mut new_up vec![0i64; m];let mut new_down vec![0i64; m];for x in 0..m {// 上升前一步为下降且结尾值 xnew_up[x] prefix_down[x]; // sum(down[0..x-1])// 下降前一步为上升且结尾值 xnew_down[x] suffix_up[x 1]; // sum(up[x1..m-1])}up new_up;down new_down;}let total (up.iter().sum::i64() down.iter().sum::i64()) % MOD;total as i32}}复杂度· 时间复杂度O(n \cdot m)其中 m r - l 1。· 空间复杂度O(m)。说明· 用 up[x] 表示以值 x 结尾且最后一步为上升的方案数down[x] 同理为下降。· 利用前缀和与后缀和将转移优化到 O(m) 每轮整体 O(n \cdot m)。· 取模 10^97返回值转为 i32。· 当 n1 时任意单个元素均满足条件直接返回 m。
