2022-11-03：给定一个数组 arr，和一个正数 k 如果 arr[i] == 0，表示 i 这里既可以是左括号也可以是右括号， 而且可以涂上 1~k 每一种颜色 如果 arr[i] != 0，表示 i 这里已经确

use std::iter::repeat;
use rand::Rng;fn main() {    let nn: i32 = 5;    let kk: i32 = 4;    let test_time: i32 = 1000;    println!("测试开始");    for _i in 0..test_time {        let n = (rand::thread_rng().gen_range(0, nn) + 1) << 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!("arr = {:?},k = {}", arr, k);            println!("ans1 = {}", ans1);            println!("ans2 = {}", ans2);            println!("出错了!");            break;        }    }    println!("测试结束");}
// 暴力方法// 为了验证fn ways1(arr: &mut Vec<i32>, k: i32) -> i32 {    if arr.len() & 1 != 0 {        return 0;    }    return process1(arr, 0, k);}
fn process1(arr: &mut Vec<i32>, index: i32, k: i32) -> i32 {    if index == arr.len() as i32 {        let n = arr.len() as i32;        let mut stack: Vec<i32> = repeat(0).take(n as usize).collect();        let mut size = 0;        for i in 0..n {            if arr[i as usize] > 0 {                stack[size as usize] = arr[i as usize];                size += 1;            } else {                if size == 0 {                    return 0;                }                size -= 1;                if stack[size as usize] != -arr[i as usize] {                    return 0;                }            }        }        return if size == 0 { 1 } else { 0 };    } else if arr[index as usize] != 0 {        return process1(arr, index + 1, k);    } else {        let mut ans = 0;        for color in 1..=k {            arr[index as usize] = color;            ans += process1(arr, index + 1, k);            arr[index as usize] = -color;            ans += process1(arr, index + 1, k);            arr[index as usize] = 0;        }        return ans;    }}
fn ways2(arr: &mut Vec<i32>, k: i32) -> i32 {    let n = arr.len() as i32;    if n & 1 != 0 {        return 0;    }    let a = combines(arr);    let mut b = 0;    for num in arr.iter() {        if *num != 0 {            b += 1;        }    }    return if ((n - (b << 1)) >> 1) < 0 {        0    } else {        a * k.pow(((n - (b << 1)) >> 1) as u32)    };}
// 忽略染色这件事，求合法的括号结合数量fn combines(arr: &mut Vec<i32>) -> i32 {    let n = arr.len() as i32;    let mut dp: Vec<Vec<i32>> = repeat(repeat(-1).take(n as usize).collect())        .take(n as usize)        .collect();    return f(arr, 0, 0, &mut dp);}
// arr[i....]范围上，去做决定// j : arr[0..i-1]已经做完决定的部分，左括号比右括号，多几个// 返回：// arr[i....]范围上，去做决定，// 已经做完决定的部分，左括号比右括号多j个// 这样的情况下，最终合法的括号结合，多少个！// process(arr, 0, 0)fn process(arr: &mut Vec<i32>, i: i32, j: i32) -> i32 {    if i == arr.len() as i32 {        return if j == 0 { 1 } else { 0 };    }    if j < 0 {        return 0;    }    // 这个不写也行    // 锦上添花的剪枝条件    if arr.len() as i32 - i < j {        return 0;    }    // arr[i] != 0    if arr[i as usize] != 0 {        // (        return process(arr, i + 1, j + 1);    } else {        // arr[i] 0 ? ( )        let p1 = process(arr, i + 1, j + 1);        let p2 = process(arr, i + 1, j - 1);        return p1 + p2;    }}
// 在arr[i...]范围上做决定// 之前在arr[0...i-1]上的决定，使得左括号比右括号多了j个// 最终合法的括号结合是多少fn f(arr: &mut Vec<i32>, i: i32, j: i32, dp: &mut Vec<Vec<i32>>) -> i32 {    let n = arr.len() as i32;    if i == n {        return if j == 0 { 1 } else { 0 };    }    if j < 0 {        return 0;    }    if n - i < j {        return 0;    }    // 如果缓存命中，直接返回答案    if dp[i as usize][j as usize] != -1 {        return dp[i as usize][j as usize];    }    let mut ans = 0;    if arr[i as usize] > 0 {        ans = f(arr, i + 1, j + 1, dp);    } else {        ans = f(arr, i + 1, j + 1, dp) + f(arr, i + 1, j - 1, dp);    }    dp[i as usize][j as usize] = ans;    return ans;}
// 生成长度随机的数组// 值在0~K之间，但是50%的概率值是0，50%的概率值是1~k中的一个fn random_array(n: i32, k: i32) -> Vec<i32> {    let mut ans = vec![];    for _ in 0..n {        ans.push(if rand::thread_rng().gen_range(0, 2) == 0 {            0        } else {            rand::thread_rng().gen_range(0, k) + 1        })    }    return ans;}