T1
题目描述
小 Z 有一个长度为 n 的非负整数序列 a ,定义一个合法的长度为 n 的非负整数序列 b 为满足对于任意的 1≤i≤n ,均满足 0≤bi≤ai 。
小 Z 想知道所有长度为 n 的满足序列异或和为 0 的合法序列 b 的数量,对 998244353 取模。
时间限制 2 s ,空间限制 512 MB 。
输入格式
输入的第一行包含一个整数 n ,表示序列 a 的长度。
输入的第二行包含 n 个整数,其中第 i 个数输入的数表示 ai 的值。
输出格式
输出一行包含一个整数,表示答案对 998244353 取模后的结果。
样例 1 输入
5
2 2 3 2 3
样例 1 输出
108
样例 2 输入
8
6 5 4 9 6 10 2 2
样例 2 输出
115804
数据范围
对于所有数据,保证 1≤n≤105,0≤ai≤109 。
测试点编号 | n≤ | ai≤ | 特殊性质 |
---|---|---|---|
1 | 10 | 5 | 无 |
2∼3 | 105 | 50 | 无 |
4∼6 | 105 | 109 | A |
7∼8 |
2000 | 109 | 无 |
9∼10 | 105 | 109 | 无 |
特殊性质 A :保证 a1>2max 。