【Bzoj1008】越狱

Description

　　监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱

Input

　　输入两个整数M，N.1<=M<=10^8,1<=N<=10^12

Output

　　可能越狱的状态数，模100003取余

Sample Input

Sample Output

HINT

　　6种状态为(000)(001)(011)(100)(110)(111)

这道题的话...思维比较强，实现起来很简单。我们这样想，所有可能性显然是m^n，但越狱的可能性我们也许不好考虑，那我们换一种思路，考虑不越狱的可能性。首先，第一个房间允许的宗教为m个，第二个只要和第一个不同，后面的都和前一个不同，就能保证相邻房间都不是同一宗教。即不越狱的可能性有m*（（m-1）^（n-1））种，最后把答案相减即可，注意取模时的细节，防止出现负数。

小学生版

#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;}