2022-12-02：有 a 块草莓蛋糕，有 b 块芝士蛋糕，两人轮流拿蛋糕， 每次不管是谁只能选择在草莓蛋糕和芝士蛋糕中拿一种， 拿的数量在 1~m 之间随意， 谁先拿完最后的蛋糕谁赢。 返回先手赢还是后手赢。

use std::iter::repeat;
fn main() {    let vv = 100;    println!("测试开始");    for a in 0..=vv {        for b in 0..vv {            for m in 0..vv {                let ans1 = who_win1(a, b, m);                let ans2 = who_win2(a, b, m);                if ans1 != ans2 {                    println!("出错了！");                    println!("a : {}", a);                    println!("b : {}", b);                    println!("m : {}", m);                    println!("ans1 : {}", ans1);                    println!("ans2 : {}", ans2);                }            }        }    }    println!("测试结束");}
// 草莓蛋糕a块// 巧克力蛋糕b块// 每次可以在任意一种上拿1~m块// 返回谁会赢，"先手" or "后手"static mut dp: [[[&str; 101]; 101]; 101] = [[[""; 101]; 101]; 101];fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a > b {        a    } else {        b    }}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a < b {        a    } else {        b    }}// 暴力方法// 为了验证fn who_win1(a: i32, b: i32, m: i32) -> &'static str {    if m >= get_max(a, b) {        // nim博弈        return if a != b { "先手" } else { "后手" };    }    if a == b {        // 蛋糕一样多        // 先手必输，因为先手不管拿什么，拿多少        // 后手都在另一堆上，拿同样多的蛋糕        // 继续让两堆蛋糕一样多        // 最终先手必输，后手必赢        return "后手";    }    if unsafe { dp[a as usize][b as usize][m as usize] } != "" {        return unsafe { dp[a as usize][b as usize][m as usize] };    }    let mut ans = "后手";    for pick in 1..=get_min(a, m) {        if who_win1(a - pick, b, m) == "后手" {            ans = "先手";        }        if ans == "先手" {            break;        }    }    for pick in 1..=get_min(b, m) {        if who_win1(a, b - pick, m) == "后手" {            ans = "先手";        }        if ans == "先手" {            break;        }    }
    unsafe {        dp[a as usize][b as usize][m as usize] = ans;    }    return ans;}
// 正式解法// 时间复杂度O(1)// 先看nim博弈fn who_win2(a: i32, b: i32, m: i32) -> &'static str {    // if m >= get_max(a, b) {    //     // nim博弈    //     return if a != b { "先手" } else { "后手" };    // }    // m < max(a,b)    if a == b {        // 蛋糕一样多        // 先手必输，因为先手不管拿什么，拿多少        // 后手都在另一堆上，拿同样多的蛋糕        // 继续让两堆蛋糕一样多        // 最终先手必输，后手必赢        return "后手";    }    // 如果 a != b    // 关注a和b的差值，    // 谁最先遇到差值为0，谁输    // 那么这就是巴什博奕    // 差值蛋糕数量共rest个。    // 每次从最少取1个，最多取m个，最后取光的人取胜。    // 如果rest=(m+1)*k + s (s!=0) 那么先手一定必胜    // 因为第一次取走s个，    // 接下来无论对手怎么取，    // 先手都能保证取到所有(m+1)倍数的点，    // 那么循环下去一定能取到差值最后一个。    let rest = get_max(a, b) - get_min(a, b);    return if rest % (m + 1) != 0 {        "先手"    } else {        "后手"    };}