bzoj 1008: [HNOI2008]越狱

公式不难推而且推出公式来以后就是一个裸快速幂了。。

个人觉得HNOI2008最水的题

 1 /*
 2 ID:WULALA
 3 PROB:bzoj1008
 4 LANG:C++
 5 */
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <algorithm>
 9 #include <cmath>
10 #include <iostream>
11 #include <fstream>
12 #include <ctime>
13 #define N 
14 #define M
15 #define mod 100003
16 #define mid(l,r) ((l+r) >> 1)
17 #define INF 0x7ffffff
18 using namespace std;
19 
20 long long n,m,ans;
21 
22 long long qpow(long long a,long long b)
23 {
24     long long cnt = 1,tot = a;
25     while(b)
26     {
27         if (b & 1) cnt *= tot;
28         if (cnt >= mod) cnt %= mod;
29         b >>= 1;
30         tot *= tot;
31         if (tot >= mod) tot %= mod;
32     }
33     return cnt;
34 }
35 
36 int main()
37 {
38     scanf("%lld%lld",&m,&n);
39     ans = qpow(m-1,n-1);
40     ans = m * ans % mod;
41     ans = qpow(m,n) - ans;
42     if (ans < 0) ans += mod;
43     printf("%lld",ans);
44     return 0;
45 }

View Code