题解 | #[HNOI2008]越狱#

题目链接

[HNOI2008]越狱

题目描述

监狱有 $N$ 个房间，按顺序编号 $1, \dots, N$ 。共有 $M$ 种宗教，每名犯人信仰其中一种。如果存在相邻房间的两名犯人信仰相同宗教，就可能发生越狱。请计算可能发生越狱的分配方案总数，结果对 $100003$ 取模。

输入:

一行输入两个整数 $M, N$ 。

输出:

输出一个整数，表示可能发生越狱的方案数量模 $100003$ 的值。

解题思路

直接计算“至少有一对相邻犯人信仰相同”的方案数比较复杂，因为需要考虑一对、两对、...、多对相邻犯人信仰相同的情况，并且它们之间有重叠，需要复杂的容斥。

遇到“至少”、“最少”这类问题时，通常可以考虑其反面，即补集思想（正难则反）。本题的“反面”问题是：所有相邻犯人的宗教信仰都不同。这也被称为“安全”或“不会发生越狱”的方案。

我们可以先计算出总的方案数和“安全”的方案数，然后用总方案数减去“安全”的方案数，即可得到“可能发生越狱”的方案数。

总方案数
- 每个房间的犯人都有 $M$ 种宗教可以选择，且互不影响。
- 根据乘法原理，总共有 $N$ 个房间，所以总方案数是 $M^N$ 。
“安全”方案数（所有相邻犯人信仰均不同）
- 第一个房间的犯人：有 $M$ 种选择。
- 第二个房间的犯人：为了与第一个犯人不同，只有 $M-1$ 种选择。
- 第三个房间的犯人：为了与第二个犯人不同，也只有 $M-1$ 种选择。
- ...
- 第 $N$ 个房间的犯人：为了与第 $N-1$ 个犯人不同，同样有 $M-1$ 种选择。
- 根据乘法原理，“安全”方案总数为 $M \cdot (M-1)^{N-1}$ 。
最终结果
- 可能发生越狱的方案数 = (总方案数) - (“安全”方案数)
- 结果 = $M^N - M \cdot (M-1)^{N-1}$

由于 $N$ 的值可能很大，直接计算幂会溢出，所以我们需要使用 快速幂 算法来计算 $M^N$ 和 $(M-1)^{N-1}$ ，并在每一步都进行取模操作。

最终的计算公式为： $(\text{power}(M, N) - (M \cdot \text{power}(M-1, N-1)) \pmod{P} + P) \pmod{P}$ 其中 power(base, exp) 是快速幂函数， $P = 100003$ 。在减法取模时加上 $P$ 是为了防止结果为负数。

代码

cpp
java
python

#include <iostream>

using namespace std;
using LL = long long;

const int MOD = 100003;

LL power(LL base, LL exp) {
    LL res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    LL m, n;
    cin >> m >> n;

    LL total = power(m, n);
    LL safe = (m * power(m - 1, n - 1)) % MOD;
    
    LL ans = (total - safe + MOD) % MOD;
    
    cout << ans << '\n';

    return 0;
}

import java.util.Scanner;

public class Main {
    static final int MOD = 100003;

    static long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long m = sc.nextLong();
        long n = sc.nextLong();

        long total = power(m, n);
        long safe = (m * power(m - 1, n - 1)) % MOD;

        long ans = (total - safe + MOD) % MOD;

        System.out.println(ans);
    }
}

MOD = 100003

m, n = map(int, input().split())

# Python's built-in pow(base, exp, mod) is efficient
total = pow(m, n, MOD)
safe = (m * pow(m - 1, n - 1, MOD)) % MOD

ans = (total - safe + MOD) % MOD

print(ans)

算法及复杂度

算法：数学、补集思想、快速幂
时间复杂度： $\mathcal{O}(\log N)$ ，主要开销来自两次快速幂计算。
空间复杂度： $\mathcal{O}(1)$ 。