PID629 / 5·21纪念日
题目描述

上个月21日(5月21日),是5·21事件一周年纪念日。为了庆祝这一天的到来,czh邀请了n个事件相关人来到Croom(一个地点)聚会。

这次聚会很奇怪。每一个进入Croom的人,都会被戴上一顶帽子,而这个人却不知道帽子的颜色。

等到被邀请的人物都到齐了,czh终于出现了。czh拿着话筒大声说道:

“我们首先来玩一个游戏,我当然不会参与。各位都看到了,到会的众位都戴着一顶帽子,有红的,也有黑的。每个人都不能看到自己的帽子的颜色,只能看到其他所有人帽子的颜色。等会儿会场的灯将全部熄灭,谁有完全的把握认为自己的帽子是红色的,谁就上台领取我为他准备的神秘礼物。如果没有人上台,那么灯将点亮,给各位一分钟的思考时间,然后又将重复上述过程,直到有人上台领奖为止。”

上述过程就这样重复着,终于在第m次熄灯之后有人上台领奖。

现在,你来猜猜一共有多少人上台领奖。

你可以假设:

1、每个人只能通过自己的推理得到帽子的颜色;

2、每个人都如czh一般聪明,在能推得自己帽子颜色的条件下一定能得到自己帽子的颜色;

3、每个人在熄灯时是否上台领奖,只决定与他在此次熄灯前的推理。

输入格式

共2行。

第1行:1个数n。

第2行:1个数m。

数据规模]

对于20%的数据,1<n <=10000。

对于100%的数据, n<=10^1000,1<=m<=n , 1<=p<=10^2

输出格式

第1行1个数p,表示有多少种可能的解。

若p>0,那么

第2~p+1行,每行1个数:若有k个人上台领奖,则输出k mod 100,000,000。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论