TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3092
  • 题目
  • P3092数字分配
    限制 : 时间限制 : 20000 MS   空间限制 : 165536 KB
    评测说明 : 1s,128m
    问题描述

    有n个整数排成一行,编号1到n。现在给你A,B两个空盒子,需要你从这n个数中取出一些数,放入A,B两个盒子里。但要求A盒子里的数字的编号必须小于B盒子中数字的编号(也就是在原始序列中,A中所有数字均在B中数字的左侧),并且每个盒子里至少要有一个数字。

    若将A盒子的所有数字进行XOR(异或)运算后的结果等于将B盒子的所有数字进行AND(与)运算的结果,我们认为这是一个“合理分配”。问,总共有多少种不同的“合理分配”方案?结果可能很大,mod 10^9+7再输出。

    输入格式

    第一行,一个整数n
    第二行,n个空格间隔的整数,表示编号1到n的数字。

    输出格式

    一行,一个整数,表示所求的答案。

    样例输入

    样例1:
    3
    1 2 3

    样例2:
    4
    1 2 3 3

    样例输出

    样例1:
    1

    样例2:
    4

    提示

    【样例1解释】
    A:1 2 (12=3)
    B:3
    【样例2解释】
    4
    1 2 3 3

    方案1:
    A:1 2 (1
    2=3)
    B:3
    方案2:
    A:1 2
    B:3
    方案3:
    A:1 2
    B:3 3
    方案4:
    A: 3
    B: 3
    【数据范围】
    n<=1000
    0 <= 给出的数字 <1024


    来源  hdu4901