洛谷3197&bzoj1008 越狱

---

---

题解

所有状态减合法状态。SBT

答案为\(m^n-m*(m-1)^{n-1}\)太SB不解释

注意取膜的问题。相减可能减出负数，而SB的C++又不给正数结果，所以要加上膜数再膜。被坑了一次。

---

Code

// It is made by XZZ#include
    
     #include
     
      #define Fname "BZOJ1008"using namespace std;#define rep(a,b,c) for(rg int a=b;a<=c;a++)#define drep(a,b,c) for(rg int a=b;a>=c;a--)#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])#define il inline#define rg register#define vd voidtypedef long long ll;il ll gi(){    rg ll x=0;rg char ch=getchar();    while(ch<'0'||ch>'9')ch=getchar();    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();    return x;}ll mod=100003;il ll quick(ll a,ll b){    ll ret=1;    while(b){        if(b&1)ret=ret*a%mod;    a=a*a%mod,b>>=1;    }return ret;}int main(){    ll m=gi(),n=gi();    printf("%lld\n",(quick(m,n)-m*quick(m-1,n-1)%mod+mod)%mod);    return 0;}