Description

　　監(jiān)獄有連續(xù)編號為1...N的N個房間，每個房間關押一個犯人，有M種宗教，每個犯人可能信仰其中一種。如果相鄰房間的犯人的宗教相同，就可能發(fā)生越獄，求有多少種狀態(tài)可能發(fā)生越獄

Input

　　輸入兩個整數M，N.1<=M<=10^8,1<=N<=10^12

Output

　　可能越獄的狀態(tài)數，模100003取余

Sample Input

Sample Output

HINT

　　6種狀態(tài)為(000)(001)(011)(100)(110)(111)

這道題的話...思維比較強，實現(xiàn)起來很簡單。我們這樣想，所有可能性顯然是m^n，但越獄的可能性我們也許不好考慮，那我們換一種思路，考慮不越獄的可能性。首先，第一個房間允許的宗教為m個，第二個只要和第一個不同，后面的都和前一個不同，就能保證相鄰房間都不是同一宗教。即不越獄的可能性有m*（（m-1）^（n-1））種，最后把答案相減即可，注意取模時的細節(jié)，防止出現(xiàn)負數。

小學生版

#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;ll k=100003;ll f(ll b,ll p){    if(p==0) return 1;    ll tmp=f(b,p/2)%k;    tmp=(tmp*tmp)%k;    if(p%2==1)    tmp=(b*tmp)%k;    return tmp;}int main(){    ll n,m,ans;    scanf("%lld%lld",&m,&n);    ans=f(m,n);    ans-=m*f(m-1,n-1)%k;     if(ans<0)    ans+=k;    PRintf("%lld",ans);    return 0;}
玄學版
#include <cstdio>#include <algorithm>using namespace std;typedef long long LL;LL mod = 100003,tot=1,cnt=1;LL m,n,tot_m,tot_n,cnt_m,cnt_n;int main(){	scanf("%lld%lld",&m,&n);	tot_m=m;tot_n=n;cnt_m=m-1;cnt_n=n-1;	while(tot_n){		if(tot_n&1) tot = (tot*tot_m)%mod;		tot_m = (tot_m*tot_m)%mod;		tot_n >>= 1;	}	while(cnt_n){		if(cnt_n&1) cnt = (cnt*cnt_m)%mod;		cnt_m = (cnt_m*cnt_m)%mod;		cnt_n >>= 1;	}	tot = tot-((cnt*m)%mod);	printf("%lld",cnt>=0? cnt:cnt+mod);	return 0;}