直接考虑越狱的话非常难处理，于是我们考虑容斥原理。

越狱情况数=总情况数-不越狱情况数。

总情况数： $m^n$。

不越狱情况数：即要求相邻两个位置都不能相同，那么第一个位置有 $m$ 种选择，第二个位置由于不能跟第一个位置相同，第二个位置有 $m-1$ 种选择，后面的位置都是 $m-1$ 种选择，即 $m \times (m-1)^{(n-1)}$。

越狱情况数：$m^n - m \times (m-1)^{(n-1)}$。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e5+3;
LL qpow(LL a,LL b){
	LL ans=1%mod;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;b>>=1;
	}
	return ans;
}
int main(){
	LL n,m;scanf("%lld%lld",&m,&n);
	printf("%lld",(qpow(m,n)-m*qpow(m-1,n-1)%mod+mod)%mod);
	return 0;
}

6种状态为(000)(001)(011)(100)(110)(111)

由于这个题目很容易看出是一道递推题，但直接硬推公式很难，所以运用容斥原理，题目问发生越狱的状态数目，我们可以用总的状态数减去不发生越狱的状态数。首先对于每一个罪犯，他都有M种宗教可以信仰，所以总的状态数为N^M，然后由于相邻的两个罪犯不能有相同的信仰(否则会发生越狱)，所以除去第1个罪犯有M种宗教可以信仰外，其他(N-1)个罪犯只有(M-1)种宗教可以信仰，这样就可以推出不发生越狱的状态数为M*(M-1)^(N-1)。综上知最终的答案S=N^M-M*(M-1)^(N-1)。

下面是程序(注意要使用快速幂，同时输入输出要使用cin,cout不然会WA)：

#include<stdio.h>
#include<iostream>
#define ll long long
using namespace std;
const int mod=100003;
ll q(ll a,ll b){
	ll s=1,r=a;
	while(b){
		if(b&1){
			s*=r;
			s%=mod;
		}
		r*=r;
		r%=mod;
		b>>=1;
	}
	return s;
}
int main(){
	ll m,n;
	cin>>m>>n;
	cout<<(q(m,n)%mod+mod-m*q(m-1,n-1)%mod)%mod<<endl;
	return 0;
}

#include<bits/stdc++.h> 
using namespace std;
 long long mod(long long m,long long n)
 { 
long long s=1;
 m%=100003; 
while(n)
 { 
if(n&1)
 s=(s%100003)*(m%100003)%100003; 
n>>=1;
 m=(m%100003)*(m%100003)%100003; 
} 
return s;
 } 
int main() 
{ 
long long m,n,x,y,z; 
scanf("%lld%lld",&m,&n);
 z=(mod(m,n)-(m%100003)*(mod(m-1,n-1)%100003)%100003+100003)%100003;
 printf("%lld",(long long)z%100003);
 }

整理版

#include<bits/stdc++.h> 
using namespace std;
 long long mod(long long m,long long n)
 { 
long long s=1;
 m%=100003; 
while(n)
 { 
if(n&1)
 s=(s%100003)*(m%100003)%100003; 
n>>=1;
 m=(m%100003)*(m%100003)%100003; 
} 
return s;
 } 
int main() 
{ 
long long m,n,x,y,z; 
scanf("%lld%lld",&m,&n);
 z=(mod(m,n)-(m%100003)*(mod(m-1,n-1)%100003)%100003+100003)%100003;
 printf("%lld",(long long)z%100003);
 }

这是一道快速幂模板题 通过手模得知，共有 mmm*m(n个m相乘),运用快速幂一下，这是总情况。

再减去不发生越狱情况就ok了！ 不发生越狱情况，每间房间都跟上一间选得不一样就行了。但第一个有m种 所以不发生越狱情况为 m*(m-1)*(m-1)...(1个m,(n-1)个(m-1)相乘)

#include<bits/stdc++.h> using namespace std; long long mod(long long m,long long n) { long long s=1; m%=100003; while(n) { if(n&1) s=(s%100003)(m%100003)%100003; n>>=1; m=(m%100003)(m%100003)%100003; } return s; } int main() { long long m,n,x,y,z; scanf("%lld%lld",&m,&n); z=(mod(m,n)-(m%100003)*(mod(m-1,n-1)%100003)%100003+100003)%100003; printf("%lld",(long long)z%100003); }//AC代码