14344: 【原4344】异或计数
题目
题目描述
author: smallling 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4344
Description
给定长度为$n$的非负整数序列$a$，问有多少个长度为$n$的非负整数序列$b$，满足：
-
$b_i \leq a_i$
-
$b_1\ xor\ b_2\ \dots\ b_n=a_1\ xor\ a_2\ \dots\ a_n$
答案对$10^9+9$取模。
Input Format
第一行一个正整数$n$。
第二行$n$个整数$a_i$。
$1 \leq n\leq 10^5,0 \leq a_i \leq 2^{30}$
Output Format
一行一个数字表示答案
Sample Input
4
1 2 3 4
Sample Output
6
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！