[bzoj1008](HNOI2008)越狱(矩阵快速幂加速递推)

 1 **************************************************************
 2     Problem: 1008
 3     User: AsmDef
 4     Language: C++
 5     Result: Accepted
 6     Time:0 ms
 7     Memory:804 kb
 8 ****************************************************************/
 9  
10 #include <cctype>
11 #include <cstdio>
12 using namespace std;
13 template<typename T>inline void getd(T &x){
14     char c = getchar(); bool minus = 0;
15     while(!isdigit(c) && c != ‘-‘)c = getchar();
16     if(c == ‘-‘)minus = 1, c = getchar();
17     x = c - ‘0‘;
18     while(isdigit(c = getchar()))x = x * 10 + c - ‘0‘;
19     if(minus)x = -x;
20 }
21 /*========================================================*/
22 const int mod = 100003;
23 typedef long long LL;
24 inline int powmod(LL x, LL k){
25     LL ans = 1;
26     while(k){
27         if(k & 1)ans = ans * x % mod;
28         x = x * x % mod;
29         k >>= 1;
30     }
31     return ans;
32 }
33 int main(){
34     #if defined DEBUG
35     freopen("test", "r", stdin);
36     #else
37     //freopen("bzoj_1008.in", "r", stdin);
38     //freopen("bzoj_1008.out", "w", stdout);
39     #endif
40      
41     LL m, n;
42     getd(m), getd(n);
43     if(n == 1){putchar(‘0‘);return 0;}
44     printf("%lld", m * (powmod(m, n-1) + mod - powmod(m-1, n-1)) % mod);
45      
46     return 0;
47 }