监狱有连续编号为 1…N1…N1…N 的 NNN 个房间，每个房间关押一个犯人，有 MMM 种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。
输入两个整数 M,NM,NM,N
输出格式：可能越狱的状态数，模 100003100003100003 取余
6种状态为(000)(001)(011)(100)(110)(111)
1≤M≤ 10^8
1≤N≤10^12
思考总数 - 合法的状态数（即邻房间的犯人的宗教不相同）；
因为每个牢房的犯人都可以信仰 m 种 宗教，所以说一共有 mnmn 种组合。
当一个牢房的犯人信仰一种宗教后，相邻的牢房的犯人只可以信仰 剩下的 m-1种 中的一种才不会越狱，即：
所以说 这是 m?(m?1)n?1m?(m?1)n?1 种；
所以说答案就是 mn?m?(m?1)n?1mn?m?(m?1)n?1
1 #include"bits/stdc++.h" 2 using namespace std; 3 typedef long long ll; 4 5 ll n,m; 6 const ll mod = 100003; 7 8 ll powmod(ll a,ll b) 9 { 10 ll base = a%mod; 11 ll ans = 1; 12 13 while (b) 14 { 15 if (b&1) ans=ans*base%mod; 16 // cout<<b<<" "<<base<<endl; 17 b>>=1; 18 base=base*base%mod; 19 20 21 22 } 23 24 return ans; 25 } 26 27 28 29 30 31 int main() 32 { 33 //cout<<powmod(2,4); 34 35 cin>>m>>n; 36 37 cout<<(powmod(m,n) -( m*powmod(m-1,n-1))%mod+mod)%100003; 38 39 }
原文：https://www.cnblogs.com/zhangbuang/p/10292968.html