TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4630
  • 题目
  • P4630黎明前的巧克力
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    评测说明 : 1s,256m
    问题描述

    Evan 和 Lyra 都是聪明可爱的孩子,两年前,Evan 开始为一个被称为UOJ的神秘的OI组织工作,在 Evan 与其他小伙伴的努力下,UOJ不仅成了OI界原创比赛的典范,更是因UR这一反人类难度的存在而举世闻名。然而今年,随着 Evan 前往世界彼岸,UOJ一天天减少着他的活力,而就在OI历新年的黎明——NOI的前夕,刚回家不久的Evan听到了清脆的敲门声……

    “开门,快递!”

    “暗号?”

    “3a34be41f8c8796c93b5c9f3b988e0d4”

    “收到!”

    送走了快递小哥,Evan 拆开包裹,看见一个写着“量子态的巧克力”的小盒子,作为新时代的OI少年,Evan 决定发扬分享的精神,于是他找来 Lyra 一起打开巧克力的盒子。

    “砰——”

    从量子态坍缩的光芒中回过神来,感受到脚下啫喱状的地板,Evan 叹了一口气——接着突然用把 Lyra 吓了一跳的音量喊了出来:

    “竟然把造题的锅塞进巧克力里!!”

    而这时,Lyra已经开始观察起了这盒奇特的巧克力,并找到了藏在巧克力盒子里的说明书。

    原来,盒子里每个巧克力都有一个味道 ai,Evan 和 Lyra 的舌头上都还没有残留任何味道(用 0 表示),当他们吃下一块巧克力的时候,舌头上的味道 b 便会异或上这个巧克力的美味值,即 bb xor a.

    Evan 和 Lyra 会各自从盒子中拿一些巧克力吃下去(即各自选择一个集合并吃掉集合中的巧克力),两个人不能吃同一块巧克力(即集合不能相交),可以有一个人选择不吃巧克力,但不能两个人都不吃。Evan 和 Lyra 不需要把盒子里的巧克力都吃完,有剩余也是可以的。

    最后如果二人舌头上残留着相同的味道,则称两人是心情契合的。

    既然量子态有无数种可能性,走出这巧克力迷局的关键就是,求出有多少种方案使得两人是心情契合的,两种方案不同当且仅当 Evan 或 Lyra 选择吃下的巧克力集合不一样。

    你只需要输出方案数对 998244353 取模的结果即可。

    输入格式

    第一行一个正整数 n ,表示巧克力的个数。

    第二行 n 个整数 ai 表示每个巧克力的美味值。

    输出格式

    输出一行一个整数,表示能使得他们心情契合的吃巧克力的方案数对 998244353 取模的结果。

    样例输入 1

    3
    1 2 3

    样例输出 1

    8

    无论 Evan 选哪个集合,Lyra 都要选 Evan 的补集。

    样例输入 2

    6
    1 2 3 4 5 6

    样例输出 2

    80

    提示

    对于全部数据,1≤n≤10^6; 0≤ai≤10^6.


    来源  UOJ310