监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果
相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱Input
输入两个整数M，N.1<=M<=10^8,1<=N<=10^12
Output
可能越狱的状态数，模100003取余
Sample Input
2 3
Sample Output
6
Hint
6种状态为(000)(001)(011)(100)(110)(111)
1 #include<iostream> 2 #include<cstdio> 3 #define LL long long 4 5 using namespace std; 6 7 const int p=100003; 8 9 LL pow(LL a,LL b) 10 { 11 LL re=1,base=a%p; 12 while(b) 13 { 14 if(b&1) 15 re=(re*base)%p; 16 base=(base*base)%p; 17 b>>=1; 18 } 19 20 return re; 21 } 22 23 int main() 24 { 25 LL m,n; 26 while(~scanf("%lld%lld",&m,&n)) 27 { 28 long long ans=pow(m,n)%p-pow(m-1,n-1)*m%p; 29 if(ans<0) 30 ans+=p; 31 printf("%lld\n",ans%p); 32 } 33 34 return 0; 35 }
原文：http://www.cnblogs.com/xibeiw/p/7394484.html