bzoj 1008 越狱

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1008

题解：

　　数学蒟蒻表示推导不能，看了题解才明白……

　　总方案数为mⁿ，第一个人有m种选择，之后每个人都有m-1种选择，所以不发生越狱的方案数为m*(m-1)^n-1

　　快速幂求解即可

　　不开long long见祖宗，十年OI一场空！

 1 #include<cstdio>
 2 #define LL long long
 3 #define MOD 100003
 4 LL m,n;
 5 LL qp(LL a,LL b)
 6 {
 7     LL ans=1;
 8     for(;b;b>>=1,a=a*a%MOD)
 9     {
10         if(b&1)ans=ans*a%MOD;
11     }
12     return ans;
13 }
14 int main()
15 {
16     scanf("%lld%lld",&m,&n);
17     LL ans=(qp(m,n)%MOD-(m*qp(m-1,n-1))%MOD)%MOD;
18     if(ans<0)ans+=MOD;
19     printf("%lld
",ans);
20     return 0;
21 }