水得不能再水了吧。此题主要是一个补集思想。
可能发生越狱的状态=所有状态-不会发生越狱的状态=M^N-M*(M-1)^(N-1)。
(M^N-M*(M-1)^(N-1))%P=(M^N%P-M*(M-1)^(N-1)%P+P)%P。
用快速幂来求解。
#include<cstdio> #define P 100003 typedef long long ll; ll n,m; ll work(ll x,ll y){ ll now=x,ans=1; for(;y;y>>=1,now=now*now%P) if(y&1) ans=ans*now%P; return ans; } int main(){ scanf("%lld%lld",&m,&n); printf("%lld",(work(m%P,n)-m*work((m-1)%P,n-1)%P+P)%P); return 0; }
原文：http://www.cnblogs.com/AmnesiacVisitor/p/7592019.html