2023-07-09：给定 N、M 两个参数，一共有 N 个格子，每个格子可以涂上一种颜色，颜色在 M 种里选，当涂满 N 个格子，并且 M 种颜色都使用了，叫一种有效方法。求一共有多少种有效方法。 1 ＜= N,

作者：福大大架构师每日一题

2023-07-09
北京
本文字数：4001 字
阅读完需：约 13 分钟

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 = 5001const 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;}