TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3377
  • 题目
  • P3377【2015重庆省队训练赛Round14】信心题
    限制 : 时间限制 : 60000 MS   空间限制 : 262144 KB
    评测说明 : 2s
    问题描述

        有两个定义在全集U的所有子集上,值为整数的函数f(S),g(S),他们之间满足这样的关系:

        设n=|U|,以下均采用0,1,2,...,2n-1来表示U的各子集。
        由于输入量巨大,我们只输入n,a0,a1,A,B,C,D,E,采用下面的方法生成整数序列{ai}:
                  ai=((A×ai-1+B×ai-2+C)and D)xor E (i>=2)
        现在给出f,求g。序列{ai}的前2n项(下标从0到2n-1)就是所给出的函数值。

    输入格式

        第一行两个数case,n,表示任务的种类和规模。
        第二行,包含七个整数a0,a1,A,B,C,D,E。

    输出格式

        只有一行,包含一个整数,表示所有g(S)异或后的值。

    样例输入

    样例输入1
    1 1
    3 4 0 0 0 0 0

    样例输入2
    2 1
    3 4 0 0 0 0 0

    样例输入3
    3 1
    3 4 0 0 0 0 0

    样例输出

    样例输出1
    4

    样例输出2
    9

    样例输出3
    17

    提示

    样例解释1
        可以算出,f(0)=3,f(1)=4,g(0)=3,g(1)=7。
    样例解释2
        可以算出,f(0)=3,f(1)=4,g(0)=3,g(1)=10。
    样例解释3
        可以算出,f(0)=3,f(1)=4,g(0)=9,g(1)=24。
    数据范围
        测试点1-6满足case=1,且n分别为12,14,16,18,20,22。
        测试点7-13满足case=2,且n分别为10,12,14,16,18,20,22。
        测试点14-20满足case=3,且n分别为7,9,11,13,15,17,19。
        对于所有测试点,0<=a0,a1,A,B,C,D,E<215