这道题数据范围给的比较大，1<=M<=10^8,1<=N<=10^12
所以不是模拟/枚举/暴力/正常做法，应该是O(1)或者log级别的。。。
一看，好像有好多种情况，所以不能用O(1)的数学方法
应该是组合计数，所以是快速幂
可能的次数为m^n种，但是会有重复的可能，所以要减去重复的次数(m-1)^(n-1)
加个优化，将m^n优为(m%100003)^n，但是可能会导致比重复的次数多，所以要加上100003，然后再%100003，这对答案是不影响的
#include<bits/stdc++.h>
#define mod 100003
long long n,m;
long long solve(long long x,long long y){
long long now=x,ans=1;
for(;y;y>>=1,now=now*now%mod)if(y&1) ans=ans*now%mod;
return ans;
}
int main(){
scanf("%lld%lld",&m,&n);
printf("%lld",(solve(m%mod,n)-m*solve((m-1)%mod,n-1)%mod+mod)%mod);
return 0;
}
原文：http://www.cnblogs.com/heqingyu/p/7683016.html