bzoj 1008: [HNOI2008]越狱

 1 /*
 2  * Problem: BZOJ 1008 
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/4/28 星期二 16:29:02
 5  * File Name: 233.cpp
 6  * State: Accepted
 7  * Memo: 容斥
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 typedef long long int64;
17 
18 const int MOD=1e5+3;
19 
20 int64 M, N;
21 int64 pow(int64 a, int64 n, int64 mod) {
22     int64 res=1;
23     while(n) {
24         if(n&1) res=(res*a)%mod;
25         a=(a*a)%mod;
26         n>>=1;
27     }
28     return res;
29 }
30 int main() {
31 #ifndef ONLINE_JUDGE
32     freopen("in", "r", stdin);
33     //freopen("out", "w", stdout);
34 #endif
35     while(~scanf("%lld%lld", &M, &N)) {
36         int64 ans=M*(pow(M, N-1, MOD)-pow(M-1, N-1, MOD))%MOD;
37         printf("%lld\n", (ans+MOD)%MOD);
38     }
39     return 0;
40 }