题解 | #[HNOI2008]越狱#

题目链接

[HNOI2008]越狱

题目描述

监狱有 $N$ 个房间，每个房间关押一名犯人，共有 $M$ 种宗教。如果相邻房间的犯人信仰同一种宗教，则可能发生越狱。请求出可能发生越狱的方案总数，结果对 $100003$ 取模。

解题思路

直接计算“至少有一对相邻犯人信仰相同”的方案数比较复杂，需要考虑多种情况并应用容斥原理。一个更简洁的思路是采用补集转化，即正难则反。

补集思想

“可能发生越狱”的对立面是“绝对不会发生越狱”。

总方案数：没有任何限制的情况下，每个犯人都有 $M$ 种宗教选择，且相互独立。根据乘法原理，总的分配方案数为 $M^N$ 。
不发生越狱的方案数：这种情况要求所有相邻房间的犯人信仰都不同。我们可以从第一个房间开始依次安排：
- 第一个犯人：有 $M$ 种选择。
- 第二个犯人：为了与第一个犯人不同，只有 $M-1$ 种选择。
- 第三个犯人：为了与第二个犯人不同，也只有 $M-1$ 种选择。
- ...
- 第 $N$ 个犯人：为了与第 $N-1$ 个犯人不同，同样有 $M-1$ 种选择。
因此，不发生越狱的总方案数为 $M \cdot (M-1)^{N-1}$ 。

最终公式

根据补集思想，“可能发生越狱”的方案数等于“总方案数”减去“不发生越狱的方案数”。

\text{Ans} = (M^N - M \cdot (M-1)^{N-1}) \pmod{100003}

快速幂

由于 $N$ 的值可能很大，直接计算幂次会超时。我们需要使用快速幂算法来高效地计算 $a^b \pmod p$ 。快速幂利用了二进制拆分的思想，可以将计算幂的时间复杂度从 $\mathcal{O}(b)$ 优化到 $\mathcal{O}(\log b)$ 。

在进行减法取模时，需要注意处理结果为负数的情况，标准的处理方式是 (a - b + mod) % mod。

代码

c++
java
python

#include <iostream>

using namespace std;

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

int main() {
    long long m, n;
    cin >> m >> n;
    
    long long mod = 100003;
    
    long long total_schemes = power(m, n);
    long long no_escape_schemes = (m * power(m - 1, n - 1)) % mod;
    
    long long ans = (total_schemes - no_escape_schemes + mod) % mod;
    
    cout << ans << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static long power(long base, long exp) {
        long res = 1;
        long mod = 100003;
        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 mod = 100003;
        
        long total_schemes = power(m, n);
        long no_escape_schemes = (m * power(m - 1, n - 1)) % mod;
        
        long ans = (total_schemes - no_escape_schemes + mod) % mod;
        
        System.out.println(ans);
    }
}

def power(base, exp):
    res = 1
    mod = 100003
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp //= 2
    return res

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

mod = 100003

total_schemes = power(m, n)
no_escape_schemes = (m * power(m - 1, n - 1)) % mod

ans = (total_schemes - no_escape_schemes + mod) % mod

print(ans)

算法及复杂度

算法：组合数学、补集思想、快速幂
时间复杂度：主要开销来自于两次快速幂运算，每次的复杂度为 $\mathcal{O}(\log N)$ 。因此，总时间复杂度为 $\mathcal{O}(\log N)$ 。
空间复杂度：只使用了常数个变量，空间复杂度为 $\mathcal{O}(1)$ 。