首页 > 代码库 > bzoj 1008
bzoj 1008
1008: [HNOI2008]越狱
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 4548 Solved: 1935
[Submit][Status]
Description
监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱
Input
输入两个整数M，N.1<=M<=10^8,1<=N<=10^12
Output
可能越狱的状态数，模100003取余
Sample Input
2 3
Sample Output
6
HINT
6种状态为(000)(001)(011)(100)(110)(111)
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cstdlib>#include<cmath>#include<algorithm>#include<queue>#include<vector>#include<set>using namespace std;#define INF 1<<30#define mod 100003#define ll long longusing namespace std;ll m,n;ll pow(ll a,ll b){ ll c=1,d=a%mod; while (b>0) { if (b&1) c=c*d%mod; b>>=1; d=d*d%mod; } return c;}int main(){ scanf("%lld%lld",&m,&n); long long ans=pow(m,n); ans=ans-m*pow(m-1,n-1)%mod; if (ans<0) ans+=mod; printf("%lld\n",ans); return 0;}
bzoj 1008
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。