没人发题解吗，本蒟蒻来shui一下（第一篇，大佬勿喷……）

其实差不多就是快速幂的模板题

因为直接算越狱的方案总数不太好搞

考虑用总方案数减去不可能越狱的方案数

代码下贴：

#include<cstdio>

#include<iostream>

using namespace std;

const int MOD=100003;

typedef long long ll;

ll exp(ll a,ll b){

ll base=1;
while (b){
if (b&1) base=base*a%MOD;
b>>=1;
a=a*a%MOD;
}
return base%MOD;//快速幂
}

ll n,m;

int main(){

scanf("%lld%lld",&m,&n);
ll ans=(exp(m,n)-(m%MOD*exp(m-1,n-1))%MOD)%MOD;//总方案数减去不可能越狱的方案数
if (ans<0) ans+=MOD;
printf("%lld",ans);
return 0;
}

组合数经典题

#include<bits/stdc++.h>
using namespace std;
const int mod=100003;
long long int n,m,k,ans,sum,s,t;
long long int q_pow(long long int x,long long int y)
{
    long long int p=1;
    while(y>0)
    {
       if(y&1)
       { 
          p=(p*x)%mod;
       } 
       x=(x*x)%mod;
       y>>=1;   
    }
    return p;
}
int main()
{
    cin>>m>>n;
    s=q_pow(m,n);
    t=(m * q_pow(m - 1, n - 1)) % mod;
    cout<<(s-t+mod)%mod;
    return 0;
}