这个问题可以通过计算“总方案数”减去“不越狱方案数”来得出结果。
总分配方案数：
每个房间有 $M$ 种宗教选择，共有 $N$ 个房间。
总数 = $M \times M \times \dots \times M = M^N$。
不越狱方案数:
第 1 个房间有 $M$ 种选择；
第 2 个房间为了不与第 1 个重复，有 $M-1$ 种选择；
第 3 个房间为了不与第 2 个重复，有 $M-1$ 种选择；
以此类推，剩下的 $N-1$ 个房间每个都有 $M-1$ 种选择。
不越狱总数 = $M \times (M-1)^{N-1}$。
可能发生越狱的方案数：
越狱方案 = 总方案数 - 不越狱方案数
结果 = $M^N - M \times (M-1)^{N-1}$
流程图
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
private static final long MOD = 100003L;
public static void main(String[] args) throws IOException {
// 使用BufferedReader读取输入，PrintWriter输出结果
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
String[] str = br.readLine().split("\\s+");
long M = Long.parseLong(str[0]);
long N = Long.parseLong(str[1]);
long total = mypower(M, N, MOD);
long safe = M * mypower(M - 1, N - 1, MOD)%MOD;
long ans = (total-safe+MOD)%MOD;
out.println(ans);
out.flush();
out.close();
br.close();
}
private static long mypower(long base, long exp, long mod) {
long ans = 1 % mod;
while (exp > 0) {
if (exp % 2 == 1) {
ans = (ans * base) % mod;
}
base = (base * base) % mod;
exp /= 2;
}
return ans;
}
|