ops，又是一道水水的，再下去我估计要被水给淹了。。。

最最最最最最简单的组合数学。。

题目：  http://www.lydsy.com/JudgeOnline/problem.php?id=1008

考虑不能越狱的情况，对于某一间，只用考虑上一间的状况，即不能选择和上一间一样的宗教

所以不能越狱的总数为 m*(m-1)^(n-1)

然后用所有排列减一减

ans=m^n-m*(m-1)^(n-1)

484很水。。。

23行的代码好久没写啦，爽爽爽~~~

#include <iostream>
#include <cstdio> 
#define mod 100003
#define ll long long
using namespace std;

long long ans;
long long n,m;

long long ksm(long long xx,long long yy) //xx^yy
{
	long long sum=1;
	for (;yy;yy>>=1) { if (yy&1) sum=sum*xx%mod; xx=xx*xx%mod; }
	return sum;
}

int main()
{
	scanf("%lld%lld",&m,&n);
	ans=(ksm((ll)m,(ll)n)%mod-m*ksm((ll)m-1,(ll)n-1)%mod+mod)%mod;
	printf("%lld\n",ans);
	return 0;
}

然而坑爹的地方就在 ans=(ksm((ll)m,(ll)n)%mod-m*ksm((ll)m-1,(ll)n-1)%mod+mod)%mod; 

为什么要加一个mod呢，因为它有负数，然而不能输出负数所以就坑了QAQ

PS.坚持都用long long 吧，有利身心健康