[P3197 [HNOI2008]越狱](https://www.luogu.org/problemnew/show/P3197)
## 题外话
$HNOI2008$，出现了一道普及+/提高——也就是这题。
$HNOI2018$，也出现了一道普及+/提高——[P4438 [HNOI/AHOI2018]道路](https://www.luogu.org/problemnew/show/P4438)
时隔十年，$HNOI$再次出现普及+/提高！
当然我都没有扫一眼然后切掉，尴尬+药丸。。。
## 正题
直接算越狱的方案总数不太好搞。
考虑用总方案数减去不可能越狱的方案数。
有$n$个房间，每个房间有$m$种可能，可以得到总方案数$=m^n$
然后就是不可能越狱的方案：
如果两个房间的的宗教相同，就可能越狱。
也就是要求相邻的两个房间宗教不同。
那么第一个房间有$m$种可能,下一个房间只要与前一个房间不同就可以了：有$m-1$种可能。
所以不越狱的方案总数$=m(m-1)^{n-1}$
然后答案就$=m^{n}-m(m-1)^{n-1}$
最后注意计算时取模就可以了。
但是要注意下最后答案为负数的情况。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MOD 100003LL
using namespace std;
long long n,m;
inline long long read(){
long long date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
long long mexp(long long a,long long b,long long c){
long long s=1;
while(b){
if(b&1)s=s*a%c;
a=a*a%c;
b>>=1;
}
return s;
}
int main(){
m=read();n=read();
printf("%lld\n",(mexp(m,n,MOD)-mexp(m-1,n-1,MOD)*(m%MOD)%MOD+MOD)%MOD);
return 0;
}
```