TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2931
  • 题目
  • P2931【THOI2014】超立方体
    限制 : 时间限制 : 250000 MS   空间限制 : 524288 KB
    评测说明 : 512MB
    问题描述

        B君得到了一个神奇的超立方体,具体来说这是一个m维的超立方体,一共有n=2m个顶点,我们将这些点从0到n-1标号。
        对于点i,我们可以吧i转换为m位二进制表示,如果不足m位则高位补0。这样得到的一个m维坐标就是这个点的坐标。
        如果两个点的欧几里得距离为1(也就是说,在原先的超立方体中有一条边连接他们),那么他们是相邻的。
        点i有pi的信息,每过一个周期,每个点都会向相邻节点发送这些信息,且自己不保留这些信息。具体来说,点i的信息总和变为它相邻的m个点的信息和。
        现在B君已知n个点的初始信息pi,他想语言t个周期之后所有点的信息分别是多少。
        B君对此一筹莫展,于是找到了他的好朋友R君。
        R君:“n和t有多大?”
        B君:“n大约220,t大约1018。”
        R君:“那这个结果太大了,即便算出来,也根本存不下。”
        B君:“那么就将最终结果模一个数把。”
        R君:“那我再想想看。”

    输入格式

    第一行三个整数n,t,K。
    以下n行,每行一个整数pi,含义如题目描述。

    输出格式

    一共n行,每行一个整数qi,表示t个周期后i节点信息总和除以K的余数。

    样例输入

    4 2 10007
    4
    1
    2
    3

    样例输出

    14
    6
    6
    14

    提示

    样例解释:
    t=0时,p[]={4,1,2,3}
    t=1时,p[]={3,7,7,3}
    t=2时,p[]={14,6,6,14}

    数据范围:
    K<=231-1,0<=pi<K,
    令m=log2n,

    
    ┏━━━━┳━━┳━━━━┳━━━━━━━━━━━━━━━━━━━━━━┓
    ┃编号┃m=┃t<= ┃       其他约定       ┃
    ┣━━━━╋━━╋━━━━╋━━━━━━━━━━━━━━━━━━━━━━┫
    ┃  1 ┃10┃1000┃                      ┃
    ┣━━━━╋━━╋━━━━┫                      ┃
    ┃  2 ┃15┃ 10 ┃                      ┃
    ┣━━━━╋━━╋━━━━┫                      ┃
    ┃  3 ┃5 ┃    ┃                      ┃
    ┣━━━━╋━━┫    ┃                      ┃
    ┃  4 ┃5 ┃    ┃                      ┃
    ┣━━━━╋━━┫    ┃                      ┃
    ┃  5 ┃6 ┃    ┃                      ┃
    ┣━━━━╋━━┫    ┃         N/A          ┃
    ┃  6 ┃6 ┃    ┃                      ┃
    ┣━━━━╋━━┫    ┃                      ┃
    ┃  7 ┃7 ┃    ┃                      ┃
    ┣━━━━╋━━┫    ┃                      ┃
    ┃  8 ┃7 ┃    ┃                      ┃
    ┣━━━━╋━━┫    ┃                      ┃
    ┃  9 ┃9 ┃    ┃                      ┃
    ┣━━━━╋━━┫    ┃                      ┃
    ┃ 10 ┃10┃    ┃                      ┃
    ┣━━━━╋━━┫10^18┣━━━━━━━━━━━━━━━━━━━━━━┫
    ┃ 11 ┃13┃    ┃ 最开始时,有超过20个 ┃
    ┣━━━━╋━━┫    ┃  点上面没有任何信息  ┃
    ┃ 12 ┃15┃    ┃                      ┃
    ┣━━━━╋━━┫    ┣━━━━━━━━━━━━━━━━━━━━━━┫
    ┃ 13 ┃17┃    ┃  最开始时,仅有5个   ┃
    ┣━━━━╋━━┫    ┃     点上存有信息     ┃
    ┃ 14 ┃19┃    ┃                      ┃
    ┣━━━━╋━━┫    ┣━━━━━━━━━━━━━━━━━━━━━━┫
    ┃ 15 ┃11┃    ┃                      ┃
    ┣━━━━╋━━┫    ┃                      ┃
    ┃ 16 ┃12┃    ┃                      ┃
    ┣━━━━╋━━┫    ┃                      ┃
    ┃ 17 ┃14┃    ┃                      ┃
    ┣━━━━╋━━┫    ┃         N/A          ┃
    ┃ 18 ┃16┃    ┃                      ┃
    ┣━━━━╋━━┫    ┃                      ┃
    ┃ 19 ┃18┃    ┃                      ┃
    ┣━━━━╋━━┫    ┃                      ┃
    ┃ 20 ┃20┃    ┃                      ┃
    ┗━━━━┻━━┻━━━━┻━━━━━━━━━━━━━━━━━━━━━━┛
    

    每个测试点的K值的奇偶性与测试点编号相同