题目名称	748. [HNOI 2008] 越狱
输入输出	`prisona.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	Makazeu 于2012-04-06加入
开放分组	全部用户
提交状态
分类标签	数学快速幂排列组合
	分享题解

通过：139，提交：383，通过率：36.29%
Hakurou!	100	0.000 s	0.00 MiB	C++
521	100	0.000 s	0.00 MiB	C++
LGLJ	100	0.000 s	0.00 MiB	C++
qyd	100	0.000 s	0.00 MiB	C++
Ezoi_XY	100	0.000 s	0.15 MiB	Pascal
苏轼	100	0.000 s	0.17 MiB	Pascal
传奇	100	0.000 s	0.17 MiB	Pascal
筽邝	100	0.000 s	0.17 MiB	Pascal
helloworld123	100	0.000 s	0.17 MiB	Pascal
helloworld123	100	0.000 s	0.17 MiB	Pascal

关于越狱的近10条评论(全部评论)
感谢楼上对可能输出负数的提醒 qyd 2022-10-16 10:58 13楼
想不通 ----------- 想通了 JustWB 2017-10-24 21:47 12楼
居然真的是快速幂qwq 芒硝 2017-10-12 19:35 11楼
AntiLeaf 2017-05-25 15:40 10楼
半星提交6次这根本不是半星QAQ 安呐一条小咸鱼。 2016-07-14 07:42 9楼
unsigned long long无负数！！！！！！！！！！！！！ Go灬Fire 2016-07-10 16:59 8楼
这还真的和快速幂有关系.. 膜拜楼上神犇唯一一个C++飘过~~~~~~~~~~~~~~~~~~~~~~~ Hakurou! 2016-07-04 10:32 7楼
如果用m^n%100003-(m-1)^(n-1)*m%100003的话，注意不要输出负数啊。 liu_runda 2015-09-29 10:26 6楼
快速幂中定义了int，传过去的却是long long，调半天、、乌龙猹 2014-10-30 06:32 5楼
回复 @元太祖 : 原来答案是pow(m,n)-pow(m-1,n-1)*m…… 水中音 2014-10-25 19:58 4楼

748. [HNOI 2008] 越狱

★☆ 输入文件：prisona.in 输出文件：prisona.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

在X星球上有一个名为Y的国家，它以治安条件良好、百姓安居乐业而闻名。正因为如此，在Y国犯罪人数很少，以至于全国只需要设置一个监狱就足够关押所有犯人。Y国的监狱很有特点：它由$n$个房间组成，所有的房间都紧挨着排成一排，而且每个房间只关押一个犯人。同时，Y国是一个多宗教的国家，其境内流行着$m$种宗教，并且每个公民都只信奉其中的一种宗教。

然而，近年来，Y国的监狱里时不时发生了犯人越狱的事件，这令Y国安全部长小K十分恼火。经过长期的调查，小K发现，发生越狱事件必须具备两个条件：首先，一个人的力量是有限的，因此越狱必须由两个相邻房间的犯人共同给策划来完成；其次，两个拥有不同宗教信仰的人是不可能互相交流的，自然也不会共同策划越狱。

了解到这些情况后，小K十分高兴。他想知道，到底有多少种情况会导致越狱事件的发生。可是，小K数数的功夫自然比不过抓犯人的本事，于是他找到了准备参加NOI2008的你，请你编写一个程序，计算在所有房间都关满犯人的条件下(即，总共关押了$n$个犯人)，有多少种监狱的状态可能导致犯人越狱。

说明：

1、越狱事件发生的充要条件是：存在两个相邻的房间，里面关押着两个拥有相同宗教信仰的人；

2、一种“监狱的状态”是指一个$n$元组$(a_1,a_2,\cdots,a_n)$，其中$0\leq a_i\leq m-1$，表示第$i$个房间的犯人拥有第$a_i$种宗教信仰。

【输入格式】

输入只包含两个用空格隔开整数，第一个整数表示宗教的种数$m$，第二个整数表示监狱种的房间数$n$。其中，$1\leq m\leq 10^8,1\leq n\leq 10^{12}$。

【输出格式】

输出仅包含一个整数，表示有多少种监狱的状态可能导致犯人越狱。由于这个数可能非常大，你只需输出它模$100003$的余数即可。

【输入样例】

2 3

【输出样例】

【样例解释】

6种状态为(000)(001)(011)(100)(110)(111)