给定N、M两个参数，
一共有N个格子，每个格子可以涂上一种颜色，颜色在M种里选，
当涂满N个格子，并且M种颜色都使用了，叫一种有效方法。
求一共有多少种有效方法。
1 <= N, M <= 5000。
返回结果比较大，请把结果 % 1000000007 之后返回。
这两种算法用于计算涂色的有效方法总数。
算法 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;
}
