洛古---越狱问题【快速幂】

今天和大家讲一个洛古的算法题，我觉得还是比较有含金量的，今天给大家分享一下

题目描述

监狱有 𝑛n个房间，每个房间关押一个犯人，有 𝑚 种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

答案对 100003取模。

输入格式

输入只有一行两个整数，分别代表宗教数 𝑚 和房间数 𝑛。

输出格式

输出一行一个整数代表答案。

输入输出样例

输入        2   3                     输出   6

数据规模与约定

解题思路： 

题目中给了我们一个例子，我们就通过这个例子进行解释分析，当我们的宗教种数为2时，然后房间数位3时，在这种情况下还是比较好考虑的，下面已经详细给出了6种情况，数字就是我们每个监狱的宗教情况

但是当我们的数很小时将结果想象出来还是比较简单的，但是当我们的数很大时，我们应该如何求呢，毕竟这是一个算法题......，我们需要一个计算过程来求出这个题

其实这里用到的就是容斥思想，因为我们不容易找到符合逃狱条件的数量（情况很多很麻烦），但是如果让我们找不符合的情况，就是很简单， 跳过约束条件找到总情况就可以了，然后通过总情况减去我们不符合情况的，剩下的就是符合的情况了 我们的越狱问题就像一个集合，其中有两个条件，一个是不能越狱的情况，一种是可以越狱的情况

这样就不难写出我们的代码了

但是如果提交上面的代码，虽然没有报错，但是会超时，为什么呢？ 

我猜大家可能忘记了题目给的m和n的范围

所以说当我们数字很大的时候有可能会超时，尤其当我们使用的是时间复杂度为log(n)时，随着我们的m和n的数增大时，就会出现超时情况 所以我们需要降低我们的时间复杂度，这么就不得不使用我们的快速幂了

什么是快速幂？

快速幂就是一种高效计算幂次方的方法，相对于直接讲a乘b次，快速幂的时间复杂度为O(logn),可以大大减少我们的运算次数

这里举个栗子：  

当我们需要计算6的25次方的时候，我们通常会使用一个while循环来实现25个6进行相乘，虽然这样可以实现我们的目的，但是运行花费的时间比较多，但是当我们使用快速幂的时候，在运行上花费的时间会大量减少

但是快速幂是如何实现时间复杂度降为O(logn)的呢？

快速幂部分代码的实现：

使用快速幂和不使用的区别：

不使用快速幂的实现的代码：

使用快速幂实现的代码：

正确代码：