2022-07-07: the original array is a monotonic array with numbers greater than 0 and less than or equal to K. there may be equal numbers in it, and the overall trend is increasing. However, the number

2022-07-07： The original array is greater than 0、 Less than or equal to k The number of , Is a monotonic array ,
There may be equal numbers , The overall trend is increasing .
But the numbers in some of these positions have been replaced by 0, We need to find out all the pieces 0 Number of alternatives ：
1） Each number filled can be greater than or equal to the previous number , Less than or equal to the next number ;
2） Each number filled cannot be greater than k.
From Tencent music .

answer 2022-07-07：

Method 1 ： Dynamic programming .
Method 2 ： Mathematical methods . Use combination ,C(b-a+m,m).

The code to use rust To write . The code is as follows ：

use rand::Rng;
fn main() {
    
    let nn: i64 = 20;
    let kk: i64 = 30;
    let test_time: i32 = 10000;
    println!(" Beginning of the test ");
    for i in 0..test_time {
    
        let n = rand::thread_rng().gen_range(0, nn) + 1;
        let k = rand::thread_rng().gen_range(0, kk) + 1;
        let mut arr = random_array(n, k);
        let ans1 = ways1(&mut arr, k);
        let ans2 = ways2(&mut arr, k);
        if ans1 != ans2 {
    
            println!(" Something went wrong !{}", i);
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!(" End of test ");
}

//  Dynamic programming 
fn ways1(nums: &mut Vec<i64>, k: i64) -> i64 {
    
    let n = nums.len() as i64;
    // dp[i][j] :  altogether i Lattice , Fill in at will , But not in descending order ,j The number of species can be selected 
    let mut dp: Vec<Vec<i64>> = vec![];
    for i in 0..n + 1 {
    
        dp.push(vec![]);
        for _ in 0..k + 1 {
    
            dp[i as usize].push(0);
        }
    }
    for i in 1..=n {
    
        dp[i as usize][1] = 1;
    }
    for i in 1..=k {
    
        dp[1][i as usize] = i;
    }
    for i in 2..=n {
    
        for j in 2..=k {
    
            dp[i as usize][j as usize] =
                dp[(i - 1) as usize][j as usize] + dp[i as usize][(j - 1) as usize];
        }
    }
    let mut res = 1;
    let mut i: i64 = 0;
    let mut j: i64 = 0;
    while i < nums.len() as i64 {
    
        if nums[i as usize] == 0 {
    
            j = i + 1;
            while j < nums.len() as i64 && nums[j as usize] == 0 {
    
                j += 1;
            }
            let left_value = if i - 1 >= 0 {
    
                nums[(i - 1) as usize]
            } else {
    
                1
            };
            let right_value = if j < nums.len() as i64 {
    
                nums[j as usize]
            } else {
    
                k
            };
            res *= dp[(j - i) as usize][(right_value - left_value + 1) as usize];
            i = j;
        }
        i += 1;
    }
    return res;
}

//  Mathematical methods 
// a ~ b Choose any number in the range , You can choose the number of repetitions , Co selection m individual 
//  Select the number of schemes in the ordered sequence ：C ( m, b - a + m )
fn ways2(nums: &mut Vec<i64>, k: i64) -> i64 {
    
    let mut res = 1;
    let mut i: i64 = 0;
    let mut j: i64 = 0;
    while i < nums.len() as i64 {
    
        if nums[i as usize] == 0 {
    
            j = i + 1;
            while j < nums.len() as i64 && nums[j as usize] == 0 {
    
                j += 1;
            }
            let left_value = if i - 1 >= 0 {
    
                nums[(i - 1) as usize]
            } else {
    
                1
            };
            let right_value = if j < nums.len() as i64 {
    
                nums[j as usize]
            } else {
    
                k
            };
            let numbers = j - i;
            res *= c(right_value - left_value + numbers, numbers);
            i = j;
        }
        i += 1;
    }
    return res;
}

//  From total a A few miles , choose b Number , What is the number of methods 
fn c(a: i64, b: i64) -> i64 {
    
    if a == b {
    
        return 1;
    }
    let mut x = 1;
    let mut y = 1;
    let mut i = b + 1;
    let mut j = 1;
    while i <= a {
    
        x *= i;
        y *= j;
        let gcd = gcd(x, y);
        x /= gcd;
        y /= gcd;
        i += 1;
        j += 1;
    }
    return x / y;
}

fn gcd(m: i64, n: i64) -> i64 {
    
    if n == 0 {
    
        m
    } else {
    
        gcd(n, m % n)
    }
}

//  In order to test 
fn random_array(n: i64, k: i64) -> Vec<i64> {
    
    let mut ans: Vec<i64> = vec![];
    for _i in 0..n {
    
        ans.push(rand::thread_rng().gen_range(0, k) + 1);
    }
    ans.sort();
    for i in 0..n {
    
        ans[i as usize] = if rand::thread_rng().gen_range(0, 2) == 0 {
    
            0
        } else {
    
            ans[i as usize]
        };
    }
    return ans;
}

The results are as follows ：

---

Zuo Shen java Code