首页 > 其他 > 详细

HYSBZ - 1008 一行

时间:2017-08-19 09:52:21      阅读:221      评论:0      收藏:0      [点我收藏+]

监狱有连续编号为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)

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #define LL long long 
 4 
 5 using namespace std;
 6 
 7 const int p=100003;
 8 
 9 LL pow(LL a,LL b)
10 {
11     LL re=1,base=a%p;
12     while(b)
13     {
14         if(b&1)
15             re=(re*base)%p;
16         base=(base*base)%p;
17         b>>=1;
18     }
19     
20     return re;
21 }
22 
23 int main()
24 {
25     LL m,n;
26     while(~scanf("%lld%lld",&m,&n))
27     {
28         long long ans=pow(m,n)%p-pow(m-1,n-1)*m%p;
29         if(ans<0)
30             ans+=p;
31         printf("%lld\n",ans%p);
32     }
33     
34     return 0;
35 }

 

HYSBZ - 1008 一行

原文:http://www.cnblogs.com/xibeiw/p/7394484.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!