异或函数计数

题目背景

给定若干组二进制输入及其目标输出，希望从所有输入变量中选择一个固定的子集，使每一组输入中被选中位置的异或值都等于对应目标值。请统计满足要求的选择方案数。

题目描述

给定一个包含 $R$ 行、$C$ 列的二进制矩阵 $M$，以及一个长度为 $R$ 的二进制目标序列 $T$。

你需要选择 $C$ 个系数

$$a_0,a_1,\ldots,a_{C-1},$$

其中每个 $a_j$ 都只能取 $0$ 或 $1$。

对于矩阵的每一行 $i$，均须满足

$$(a_0\land M_{i,0})\oplus(a_1\land M_{i,1})\oplus\cdots\oplus(a_{C-1}\land M_{i,C-1})=T_i,$$

其中：

• $\land$ 表示按位与；
• $\oplus$ 表示异或。

等价地，只对所有满足 $a_j=1$ 的位置 $M_{i,j}$ 求异或，其结果必须为 $T_i$。

请计算有多少个不同的系数序列 $(a_0,a_1,\ldots,a_{C-1})$ 同时满足全部 $R$ 个等式。

输入格式

第一行包含两个整数 $R,C$，分别表示矩阵的行数和列数。

接下来 $R$ 行，每行包含一个长度为 $C$ 的二进制字符串。第 $i$ 行字符串的第 $j$ 个字符表示 $M_{i,j}$。

最后一行包含 $R$ 个整数 $T_0,T_1,\ldots,T_{R-1}$，相邻整数之间以空格分隔。

输出格式

输出一行一个整数，表示满足条件的系数序列数量。

答案保证不超过 $2^{50}$，应使用 64 位整数保存。

数据范围

• $1\le R\le 50$；
• $1\le C\le 50$；
• 矩阵中的每个字符均为 0 或 1；
• $T_i\in\{0,1\}$。

样例 1

输入

3 3
000
001
010
0 1 1

输出

2

样例 2

输入

3 3
000
001
010
1 1 1

输出

0

样例 3

输入

3 4
0000
0000
0000
0 0 0

输出

16

样例 4

输入

5 40
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0000000000000000000000000000000000000000
0 0 0 0 0

输出

1099511627776

说明

两个方案只要存在某个位置 $j$ 的系数 $a_j$ 不同，就视为不同方案。

来源

Topcoder XORing.findSubset(String[] m, int[] t)，已转换为标准输入输出形式。