2023-07-09：给定N、M两个参数，

一共有N个格子，每个格子可以涂上一种颜色，颜色在M种里选，

当涂满N个格子，并且M种颜色都使用了，叫一种有效方法。

求一共有多少种有效方法。

1 <= N, M <= 5000。

返回结果比较大，请把结果 % 1000000007 之后返回。

答案2023-07-09：

这两种算法用于计算涂色的有效方法总数。

算法 ways1：

1.初始化路径数组 path，颜色是否使用的数组 set。

2.调用 process 函数，传入初始参数：路径数组 path，颜色是否使用的数组 set，当前处理的位置 i，格子数量 n，颜色种类 m。

3.如果当前位置 i 等于格子数量 n，即路径数组 path 已填满：

• 将颜色是否使用的数组 set 中所有元素重置为 false。

• 统计路径数组 path 中不重复的颜色数量，并记录在 colors 中。

• 如果 colors 等于颜色种类 m，说明此路径是有效方法，返回 1；否则返回 0。

4.否则，遍历颜色种类 m 的所有可能颜色：

• 在路径数组 path 当前位置 i 处填入该颜色。

• 调用 process 函数递归处理下一个位置 i+1。

• 将返回的结果累加到 ans 上。

5.返回最终的结果 ans。

算法 ways2：

1.初始化动态规划数组 dp，大小为 MAXN × MAXN。

2.对于 dp 数组的第一行，设置每个位置的值为颜色种类 m。

3.使用两层循环，从第二行开始，依次计算每个位置 dp[i][j] 的值：

• dp[i][j] 等于前一行 dp[i-1][j] 乘以颜色种类 j 取模 mod。

• 添加额外的项，dp[i][j] 等于前一行 dp[i-1][j-1] 乘以剩余颜色种类 m-j+1，然后加上之前的结果，再取模 mod。

4.返回 dp[n][m] 的结果作为最终的答案。

功能测试：逐个测试从 1 到 9 的格子数量和颜色种类的组合，比较两种算法的结果是否一致，如果不一致则输出错误信息并中断。

性能测试：以 N=5000、M=4877 为例，计算两种算法的运行时间并打印结果。

算法 ways1 的时间复杂度为O(m^n)，空间复杂度为O(n)。

算法 ways2 的时间复杂度为O(nm)，空间复杂度为O(nm)。

go完整代码如下：

package main

import (
    "fmt"
    "time"
)

const MAXN = 5001
const mod = 1000000007

var dp [MAXN][MAXN]int

func ways1(n int, m int) int {
    path := make([]int, n)
    set := make([]bool, m+1)
    return process(path, set, 0, n, m)
}

func process(path []int, set []bool, i int, n int, m int) int {
    if i == n {
        for j := 0; j <= m; j++ {
            set[j] = false
        }
        colors := 0
        for _, c := range path {
            if !set[c] {
                set[c] = true
                colors++
            }
        }
        if colors == m {
            return 1
        } else {
            return 0
        }
    } else {
        ans := 0
        for j := 1; j <= m; j++ {
            path[i] = j
            ans += process(path, set, i+1, n, m)
        }
        return ans
    }
}

func ways2(n int, m int) int {
    for i := 1; i <= n; i++ {
        dp[i][1] = m
    }
    for i := 2; i <= n; i++ {
        for j := 2; j <= m; j++ {
            dp[i][j] = int((int64(dp[i-1][j]) * int64(j)) % mod)
            dp[i][j] = int((int64(dp[i-1][j-1])*(int64(m-j+1)) + int64(dp[i][j])) % mod)
        }
    }
    return dp[n][m]
}

func main() {
    N := 9
    M := 9
    fmt.Println("功能测试开始")
    for n := 1; n <= N; n++ {
        for m := 1; m <= M; m++ {
            ans1 := ways1(n, m)
            ans2 := ways2(n, m)
            if ans1 != ans2 {
                fmt.Println("出错了!")
                fmt.Println("n : ", n)
                fmt.Println("m : ", m)
                fmt.Println("ans1 : ", ans1)
                fmt.Println("ans2 : ", ans2)
                break
            }
        }
    }
    fmt.Println("功能测试结束")

    fmt.Println("性能测试开始")
    n := 5000
    m := 4877
    fmt.Println("n : ", n)
    fmt.Println("m : ", m)
    start := currentTimeMillis()
    ans := ways2(n, m)
    end := currentTimeMillis()
    fmt.Println("取余之后的结果 : ", ans)
    fmt.Println("运行时间 : ", (end - start), " 毫秒")
    fmt.Println("性能测试结束")
}

func currentTimeMillis() int64 {
    return time.Now().UnixNano() / int64(time.Millisecond)
}

rust完整代码如下：

fn ways1(n: i32, m: i32) -> i32 {
    let mut path = vec![0; n as usize];
    let mut set = vec![false; (m + 1) as usize];
    process(&mut path, &mut set, 0, n, m)
}

fn process(path: &mut [i32], set: &mut [bool], i: i32, n: i32, m: i32) -> i32 {
    if i == n {
        set.iter_mut().for_each(|x| *x = false);
        let mut colors = 0;
        for &c in path.iter() {
            if !set[c as usize] {
                set[c as usize] = true;
                colors += 1;
            }
        }
        return if colors == m { 1 } else { 0 };
    } else {
        let mut ans = 0;
        for j in 1..=m {
            path[i as usize] = j;
            ans += process(path, set, i + 1, n, m);
        }
        ans
    }
}

const MAXN: usize = 5001;

const MOD: i64 = 1000000007;

static mut DP: [[i32; MAXN]; MAXN] = [[0; MAXN]; MAXN];

fn ways2(n: i32, m: i32) -> i32 {
    unsafe {
        for i in 1..=n {
            DP[i as usize][1] = m;
        }
        for i in 2..=n {
            for j in 2..=m {
                DP[i as usize][j as usize] =
                    ((DP[(i - 1) as usize][j as usize] as i64 * j as i64) % MOD) as i32;
                DP[i as usize][j as usize] = (((DP[(i - 1) as usize][(j - 1) as usize] as i64
                    * (m - j + 1) as i64)
                    + DP[i as usize][j as usize] as i64)
                    % MOD) as i32;
            }
        }
        DP[n as usize][m as usize]
    }
}

fn main() {
    let n: i32 = 9;
    let m: i32 = 9;
    println!("功能测试开始");
    for n_val in 1..=n {
        for m_val in 1..=m {
            let ans1 = ways1(n_val, m_val);
            let ans2 = ways2(n_val, m_val);
            if ans1 != ans2 {
                println!("出错了!");
                println!("n : {}", n_val);
                println!("m : {}", m_val);
                println!("ans1 : {}", ans1);
                println!("ans2 : {}", ans2);
                break;
            }
        }
    }
    println!("功能测试结束");

    println!("性能测试开始");
    let n_val: i32 = 5000;
    let m_val: i32 = 4877;
    println!("n : {}", n_val);
    println!("m : {}", m_val);
    let start = std::time::Instant::now();
    let ans = ways2(n_val, m_val);
    let duration = start.elapsed();
    println!("取余之后的结果 : {}", ans);
    println!("运行时间 : {} 毫秒", duration.as_millis());
    println!("性能测试结束");
}

c++完整代码如下：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 5001;
const int mod = 1000000007;

vector<vector<int>> dp(MAXN, vector<int>(MAXN, 0));

int process(vector<int>& path, vector<bool>& set, int i, int n, int m);

int ways1(int n, int m) {
    vector<int> path(n, 0);
    vector<bool> set(m + 1, false);
    return process(path, set, 0, n, m);
}

int process(vector<int>& path, vector<bool>& set, int i, int n, int m) {
    if (i == n) {
        fill(set.begin(), set.end(), false);
        int colors = 0;
        for (int c : path) {
            if (!set[c]) {
                set[c] = true;
                colors++;
            }
        }
        return colors == m ? 1 : 0;
    }
    else {
        int ans = 0;
        for (int j = 1; j <= m; j++) {
            path[i] = j;
            ans += process(path, set, i + 1, n, m);
        }
        return ans;
    }
}

int ways2(int n, int m) {
    for (int i = 1; i <= n; i++) {
        dp[i][1] = m;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            dp[i][j] = ((long)dp[i - 1][j] * j) % mod;
            dp[i][j] = (((long)dp[i - 1][j - 1] * (m - j + 1)) + dp[i][j]) % mod;
        }
    }
    return dp[n][m];
}

int main() {
    int N = 9;
    int M = 9;
    cout << "功能测试开始" << endl;
    for (int n = 1; n <= N; n++) {
        for (int m = 1; m <= M; m++) {
            int ans1 = ways1(n, m);
            int ans2 = ways2(n, m);
            if (ans1 != ans2) {
                cout << "出错了!" << endl;
                cout << "n : " << n << endl;
                cout << "m : " << m << endl;
                cout << "ans1 : " << ans1 << endl;
                cout << "ans2 : " << ans2 << endl;
                break;
            }
        }
    }
    cout << "功能测试结束" << endl;

    cout << "性能测试开始" << endl;
    int n = 5000;
    int m = 4877;
    cout << "n : " << n << endl;
    cout << "m : " << m << endl;
    long long start = clock();
    int ans = ways2(n, m);
    long long end = clock();
    cout << "取余之后的结果 : " << ans << endl;
    cout << "运行时间 : " << (end - start) << " 毫秒" << endl;
    cout << "性能测试结束" << endl;

    return 0;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接