若沒了解過快速冪滥朱,請移至第數(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);
該快速冪上場表演了2闷妗!
代碼如下
#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;
}
關注點一點童叠,活到九十九?蛟?文弧!謝謝啦N蹇濉UЬ!