监狱有连续编号为1~n的n个房间，每个房间关押一个犯人。有 M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。求有多少种状态可能发生越狱。
#include<bits/stdc++.h> #define MOD 100003 #define ll long long using namespace std; ll qmi(ll x,ll y) { ll ans=1; while(y) { if(y&1)ans=ans*x%MOD; y>>=1; x=x*x%MOD; } return ans; } int main() { ll m,n; cin>>m>>n; cout<<((qmi(m,n)%MOD-m*qmi(m-1,n-1)%MOD)+MOD)%MOD; return 0; }
原文：https://www.cnblogs.com/1314cyd/p/14351551.html