【快速幂, 数学】越狱

题目

1290. 越狱 - AcWing题库

---

监狱有连续编号为 $1$ 到 $n$ 的 $n$ 个房间，每个房间关押一个犯人。

有 $m$ 种宗教，每个犯人可能信仰其中一种。

如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。

求有多少种状态可能发生越狱。

输入格式

共一行，包含两个整数 $m$ 和 $n$ 。

输出格式

可能越狱的状态数，对 $100003$ 取余。

数据范围

$1 \le m \le 10^8$ ,
$1 \le n \le 10^{12}$

输入样例：

2 3

输出样例：

6

样例解释

所有可能的 $6$ 种状态为： $(000)(001)(011)(100)(110)(111)$ 。

解题

方法一：快速幂

思路

对于每一个犯人来说，他都能选择 $m$ 种宗教，所以 $n$ 个犯人一共会有 $\prod_{i=1}^n{m} = n^m$ 种状态。

若想不发生越狱，对于第 $1$ 个房间的犯人，没有人在他左边与其相邻，所以他选择 $m$ 种宗教都不会与人发生越狱；对于第 $2 \sim n$ 个房间的犯人 $i$ ，他们都不能选择与犯人 $i-1$ 相同的宗教，所以只有 $m-1$ 种宗教供他们选择。那么 $n$ 个犯人共有 $m \cdot \prod_{i=2}^{n}{m} = m \cdot (m-1)^{n-1}$ 种状态。

综上，共有 $n^m - m \cdot (m-1)^{n-1}$ 种状态可能发生越狱。

数都比较大，所以用快速幂来取幂。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = 100003;
    
    static long qmi(long base, long exp) {
        long res = 1L;
        while (exp > 0) {
            if ((exp & 1) == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return res;
    }
    
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        long m = in.nextLong(), n = in.nextLong();
        long total = qmi(m, n);
        long not = (m * qmi(m - 1, n - 1)) % MOD;
        System.out.println((total - not + MOD) % MOD);
    }
}