1008: [HNOI2008]越獄

Time Limit:?1 Sec??Memory Limit:?162 MB
Submit:?12593??Solved:?5439
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

2 3

Sample Output

6

HINT

?

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

題目鏈接：

　　　　http://www.lydsy.com/JudgeOnline/problem.php?id=1008?

Solution

　　求可能越獄的方案數(shù)，可以用方案總數(shù)減去不可能越獄的方案數(shù)，快速冪即可。。

代碼

#include<iostream> #include<cstdio> #define LL long long using namespace std; LL n,m; LL mod; LL power(LL x,LL y){LL s=1;if(x==0) return 1;if(x&1){s=power(x/2,y);s=(s*s*y)%mod;}else{s=power(x/2,y);s=(s*s)%mod;}return s; } int main(){LL ans;mod=100003;scanf("%lld%lld",&m,&n);m=m%mod;ans=((power(n,m)-(m*power(n-1,m-1)%mod))+mod)%mod;printf("%lld\n",ans);return 0; }

　　

　　

This passage is made by Iscream-2001.

?

轉(zhuǎn)載于:https://www.cnblogs.com/Yuigahama/p/9651974.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1008--[HNOI2008]越狱（容斥快速幂）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。