Description

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

Input

　　輸入兩個(gè)整數(shù)M，N.1<=M<=10^8,1<=N<=10^12

Output

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

Sample Input

Sample Output

HINT

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

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

小學(xué)生版

#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;}
玄學(xué)版
#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;}