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;
}