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(n*m)，空间复杂度为O(n*m)。
# go完整代码如下：
```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完整代码如下：
```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++完整代码如下：
```cpp
#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;
}
```
