在一次课间休息的时候,音无结弦看到立华奏一个人坐在座位上写作业,于是动了请她吃麻婆豆腐的念头。他迅速移动到她后面的座位,寻思着该怎么开口邀请,他摸了摸口袋,拍了拍脑袋,有了!
“奏~听说食堂里有种传闻中因为辣过头所以谁都不会点的麻婆豆腐,但是却惊人地好吃啊,这样,我们来做个题吧!如果你做出来了我就天天请你吃麻婆豆腐╰(￣▽￣)╮”
奏的笔停下了,她转过头来,还带了一张草稿纸,做好了做题的准备。音无懵了一下,心中暗暗窃喜,“麻婆豆腐果然是她的最爱啊!”
“咳咳...请听题!我手上有n枚硬币,第i枚正面朝上的概率是Pi。我现在每个硬币各抛一次,正面朝上看做1,背面朝上看做0,把所有硬币得到的数异或起来决定最后得到的数。问:有多少个子集合使得0和1的概率相等?”
不管音无给了怎样的数,奏都是一分钟不到就算出来了!不愧是前学生会长啊~
于是他们就去食堂吃麻婆豆腐了,现在,你也来算一下吧。
输入描述:
输入的第一行包含一个整数T，表示测试组数。
每个测试用例前面都有一个空白行。
每个测试用例由两行组成。
第一行包含硬币数量n。
第二行包含n个数表示：概率p1,...,pn。每个pi都给出6个小数位。
输出描述:
对于每个测试用例输出一个数：使得0和1的概率相等的子集合数量。
示例1
输入
复制
2
3
0.500000 0.500000 0.500000
4
0.000001 0.000002 0.000003 0.000004
说明
在第一个测试样例中，每个子集显然都能使得0和1的概率相等。
在第二个测试样例中，所有子集都不能使得0和1的概率相等
备注:
n ≤ 60,T=500