【HNOI2008】越狱

题面

https://www.luogu.org/problem/P3197

题解

以一道水题作为“数学”部分的开端。

补集转换$+$快速幂

#include<stack>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
#define mod 100003
#define ri register int

using namespace std;

LL pow(LL a,LL b) {
  a%=mod;LL ret=1;
  for (;b;b>>=1,a=(a*a)%mod) if (b&1) ret=(ret*a)%mod;
  return ret;
}

int main() {
  LL n,m;
  scanf("%lld %lld",&m,&n);
  printf("%lld
",(pow(m,n)-(m*pow(m-1,n-1))%mod+mod)%mod);
}