题目名称 2226. 定情信物
输入输出 bzoj_3823.in/out
难度等级 ★★★
时间限制 10000 ms (10 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarasddddd 于2016-04-11加入
开放分组 全部用户
提交状态
分类标签
递推
分享题解
通过:0, 提交:2, 通过率:0%
Gravatar木留木留木 0 0.002 s 76.61 MiB C++
Gravatar加藤惠 0 0.927 s 0.31 MiB C++
关于 定情信物 的近10条评论(全部评论)

2226. 定情信物

★★★   输入文件:bzoj_3823.in   输出文件:bzoj_3823.out   简单对比
时间限制:10 s   内存限制:128 MiB

【题目描述】

都说程序员找不到妹子,可是无人知晓,三生石上竟然还刻着属于小 E 的一笔。

那一天, E 穷尽毕生的积蓄,赠与了妹子一个非同寻常的定情信物。那是一个小

小的正方体,但透过它,可以看到过去,可以洞彻天机。

这份信物仿佛一只深邃的眼。当看透它看似简单的外表后,深邃的内心却最是可以

叩击人的灵魂的。不出所料,妹子果然被这个信物超越空间的美所吸引。

易有太极,是生两仪,两仪生四象,四象生八卦。,八卦定吉凶,吉凶生大业。

这句箴言在其上得到了完美的诠释。

是的,这正是一个超正方体。

E 告诉妹子,他的情意也如这份信物一样深厚。现在妹子想知道, E 对她的情

意究竟有几分?

我们知道,点动成线,线动成面,面动成体...... n 维超立方体可看作由 n-1 维超

立方体沿垂直于它的所有的棱的方向平移得到的立体图形。

我们可以将点看作 0 维超立方体,将直线看作 1 维超立方体,将正方形看作 2 维超

立方体......依此类推。

任何一个 n 维超立方体(n>0)都是由低维的超立方体元素组成的:它的 n-1 维表面

n-1 维的超立方体,它的 n-2 维边缘是 n-2 维的超立方体,它的 n-3 维元素是 n-3 维的

超立方体......

E 对妹子的情意即为在他的定情信物——K 维超立方体中,含有每一维的元素个

数。由于元素个数可能较大,只需要输出它所包含的每一维元素个数模 P 后的异或和。

【输入格式】

两个整数 KP,详见题目叙述。

【输出格式】

一个非负整数,表示小 E 的定情信物所包含的每一维元素个数模 P 后的异或和。注

:异或和可能会大于 P

【样例输入】


 input 1

 3 7

 Input 2

 4 2333

 Input 3

 12 7723


【样例输出】


 Output1

 3

 Output 2

 33

 Output 3

 360

 Hint

 对于样例2的解释:

 一个三维超立方体含有 8 个零维元素、12 个一维元素、6 个二维元素、1 个三维

 元素,模 7 后分别为 1,5,6,1,异或和为 1^5^6^1=3。


【提示】

  对于 100%的数据,N≤10^7,P 为 10^9 内的素数。

【来源】

【题目来源】

耒阳大世界(衡阳八中) OJ 3823