【BZOJ1008】越狱（排列组合计数，容斥原理）

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #define MOD 100003
 7 typedef long long LL;
 8 using namespace std;
 9   
10 LL n,m,ans;
11   
12 LL pow(LL x,LL y)
13 {
14   LL s=1; LL tmp=x%MOD;
15   while(y)
16   {
17     if(y&1) s=s*tmp%MOD;
18     tmp=tmp*tmp%MOD; 
19     y>>=1;
20   }
21   return s;
22 }    
23   
24 int main()
25 {
26   scanf("%lld%lld",&m,&n);
27   ans=pow(m,n)-m*pow(m-1,n-1);
28   ans=(ans%MOD+MOD)%MOD;
29   printf("%lld",ans);
30   return 0;
31 }