监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果
相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1008
洛谷：https://www.luogu.com.cn/problem/P3197
监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果
相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
输入两个整数M，N.1<=M<=10^8,1<=N<=10^12
可能越狱的状态数，模100003取余
6种状态为(000)(001)(011)(100)(110)(111)
emmm，没啥好说的，推公式就完事了，首先考虑所有情况，那么就是每个位置有m种选择，即$m^{n}$，考虑没有相邻位置一样的宗教，第一个位置有m种选择，第二个位置有m-1种选择，第三位置只要和第二个位置不一样就好了，同样也是m-1中选择，也就是说不符合条件的情况有$m\times (m-1)^{n-1}$
以下是AC代码：
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; #define ll long long const ll mod=1e5+3; ll qick(ll a,ll b) { a%=mod; ll ans=1; while (b){ if (b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans%mod; } int main() { ll m,n; scanf ("%lld%lld",&m,&n); ll ans=(qick(m,n)-(m%mod)*qick(m-1,n-1)%mod+mod)%mod; printf("%lld\n",ans); return 0; }
BZOJ-1008&洛谷P3197--越狱【HNOI2008】推公式
原文：https://www.cnblogs.com/lonely-wind-/p/12191707.html