算法分析

相邻的两个房间的犯人信仰的宗教相同，就可能发生越狱
答案 = 总数 - 不可能 = $m^n - m * (m - 1)^{n - 1}$

• 总数：有n个犯人，每个犯人都可以信仰m种宗教，因此有$m^n$种情况
• 不可能：第1个犯人可以信仰m种宗教，第2个犯人可以信仰m - 1种宗教，第3个犯人可以信仰m - 1中宗教…，总共有$m * (m - 1)^{n - 1}$

时间复杂度$O(logn)$

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int mod = 100003;
    static long qmi(int a,long k)
    {
        long res = 1 % mod;
        long t = a;
        while(k > 0)
        {
            if((k & 1) != 0) res = res * t % mod;
            k >>= 1;
            t = t * t % mod;
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int m = scan.nextInt();
        long n = scan.nextLong();
        System.out.println(((qmi(m,n) - m * qmi(m - 1,n - 1)) % mod + mod) % mod);
    }
}