题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1008
(这样一道水题还因为忘记写 %lld WA了那么多遍)
发生越狱的状态数，就是全部状态减去不越狱的状态，那么就好算了；
也就是 m^n - m * (m-1)^(n-1)
代码如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef long long ll; int const mod=100003; ll n,m; ll pw(ll a,ll b) { ll ret=1ll; for(;b;b>>=1ll,a=(a*a)%mod) if(b&1)ret=(ret*a)%mod; return ret; } int main() { scanf("%lld%lld",&m,&n); m=m%mod; printf("%lld",((pw(m,n)-m*pw(m-1,n-1))%mod+mod)%mod); return 0; }
原文：https://www.cnblogs.com/Zinn/p/9265430.html