若沒了解過快速冪滥朱，請移至第數(shù)論第一篇題解 快速冪模板
題目描述
監(jiān)獄有連續(xù)編號為 1…N1…N 的 N 個房間查蓉，每個房間關押一個犯人舵抹，有 M 種宗教，每個犯人可能信仰其中一種鉴分。如果相鄰房間的犯人的宗教相同哮幢，就可能發(fā)生越獄，求有多少種狀態(tài)可能發(fā)生越獄志珍。
輸入輸出格式
輸入格式：
輸入兩個整數(shù) M,N
輸出格式：
可能越獄的狀態(tài)數(shù)橙垢，模 100003 取余
直接計算可能越獄的情況數(shù)很困難，所以我們轉換思路伦糯，先求出所有的情況柜某，再求出不可能的情況，相減即是可能的情況敛纲。喂击。
有n個監(jiān)獄，m種選擇淤翔，總方案數(shù)便是mn翰绊，第一間監(jiān)獄有m種方案，第二件因為不能和第一間一樣則第二間的方案數(shù)為m-1旁壮，第三件不能和第二間一樣监嗜，則也有m-1種，以此類推抡谐，故不可能的情況數(shù)為m(m-1)(n-1);
故答案為mn-m(m-1)(n-1);
該快速冪上場表演了２闷妗！
代碼如下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define LL long long
#include<algorithm>
using namespace std;
LL n,m,mod=100003;
LL quickPow(LL a,LL b){
LL sum=1;
while(b){
if(b&1) sum=sum*a%mod;
b>>=1;
a=a*a%mod;
}
return sum;
}
int main(){
scanf("%lld%lld",&m,&n);
LL ans1=quickPow(m,n),ans2=(m%mod*quickPow(m-1,n-1))%mod;
LL ans=ans1-ans2;
if(ans<0) ans+=mod;
printf("%lld\n",ans%mod);
return 0;
}
關注點一點童叠，活到九十九？蛟？文弧！謝謝啦Ｎ蹇濉ＵЬ！
