bzoj1008--越狱 组合数学

这个题还是很简单的，一共有M^N种情况，只要减去不可能发生越狱的情况，就是可能发生越狱的情况。
不可能发生越狱的情况：第一个犯人有M种宗教选择，第二个犯人有M-1种宗教选择（因为要与相邻的犯人不一样），第三个犯人也有M-1种宗教选择，一直到第N个犯人也有M-1种宗教选择，所以一共有M*(M-1)^(N-1)。
所以可能发生越狱的情况：M^N-M*(M-1)(N-1)=M[M^(N-1)-(M-1)(N-1)]
直接快速幂吧，很简单。

#include<cstdio>
using namespace std;typedef long long ll;
const ll mod=100003;inline ll mypow(ll a,ll b){ll sum=1;while(b){if(b&1) sum=(sum*a)%mod;a=(a*a)%mod;b>>=1;}return sum;
}int main(){ll n,m;scanf("%lld%lld",&m,&n);printf("%lld",(mypow(m,n-1)-mypow(m-1,n-1)+mod)%mod*m%mod);
}