algorithm-class/算法周更班/class_2023_03_2_week/Code03_FillCellsUseAllColorsWays.java

package class_2023_03_2_week;

import java.util.Arrays;

// 来自学员问题
// 给定N、M两个参数
// 一共有N个格子，每个格子可以涂上一种颜色，颜色在M种里选
// 当涂满N个格子，并且M种颜色都使用了，叫一种有效方法
// 求一共有多少种有效方法
// 1 <= N, M <= 5000
// 返回结果比较大，请把结果 % 1000000007 之后返回
public class Code03_FillCellsUseAllColorsWays {

	// 暴力方法
	// 为了验证
	public static int ways1(int n, int m) {
		return process(new int[n], new boolean[m + 1], 0, n, m);
	}

	public static int process(int[] path, boolean[] set, int i, int n, int m) {
		if (i == n) {
			Arrays.fill(set, 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;
		}
	}

	// 正式方法
	// 时间复杂度O(N*M)
	public static int MAXN = 5001;

	public static int[][] dp = new int[MAXN][MAXN];

	public static int mod = 1000000007;

	public static 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] = (int) (((long) dp[i - 1][j] * j) % mod);
				dp[i][j] = (int) ((((long) dp[i - 1][j - 1] * (m - j + 1)) + dp[i][j]) % mod);
			}
		}
		return dp[n][m];
	}

	public static void main(String[] args) {
		int N = 9;
		int M = 9;
		System.out.println("功能测试开始");
		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) {
					System.out.println("出错了!");
					System.out.println("n : " + n);
					System.out.println("m : " + m);
					System.out.println("ans1 : " + ans1);
					System.out.println("ans2 : " + ans2);
					break;
				}
			}
		}
		System.out.println("功能测试结束");

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

}