XOR门

Grade 0 Open Time Tuesday, 22 January 2013, 9:15 am
Discount 0.8 Time Discount Tuesday, 22 January 2013, 9:15 am
Allow late Yes Close Time Tuesday, 22 January 2013, 9:15 am
Input file xor.in Output file xor.out

一个XOR门包含两个输入和一个输出,它的工作可以用下表描述:

input 1 input 2 output
0         0        0
0         1        1
1         0        1
1         1        0

如果一个XOR门系统有n个输入和1个输出,且满足以下条件,则称这个XOR门系统为XOR网络。

  1. 系统的每一个输入都至少与一个XOR门的输入端相连;
  2. 系统中每个门的输入必须与系统的一个输入或另一个门的输出连接;
  3. 有且只有有一个门的输出与系统的输出相连;
  4. 每个门的输出要与另外至少一个门的输入或系统的输出相连;
  5. 这些XOR门存在一种编号方式,使得每个门的输入都与系统的输入或具有较小编号的门的输出相连。

例子:

Image:Xor.png

图中有一个由6个XOR门组成的XOR系统。它有5个输入和1个输出,它满足以上的5个条件,所以它是一个XOR网络。注意:图中给出的编号方式不满足条件5,但可以找到一种满足条件的编号方式。

网络的输入标号为1到5,一种输入状态可以用一个长度为n的字符串表示,每一位是0或1,我们假设第I个数字表示第I个输入的状态。每一个 输入都是一个自然数的二进制编码,所以我们可以按输入状态表示的数值的大小将它们排序。我们要测试一个电路门网络,通过向它发送一个范围以内的输入,计算 使输出是1的输入个数。

任务:

  1. 从文本文件xor.in中读入电路网的的描述。描述包括输入的个数n,XOR门的个数m,以及XOR门连接的情况。
  2. 从文件中读入两个长度为n的二进制串,表示输入的上限和下限。
  3. 计算给定范围内有多少种输入可以使输出为1。
  4. 将结果写入文件xor.out。

我们假设3 < n < 100, 3 < m < 3000,而且网络中的门是用1到m之间的数任 意编号的。

输入格式: 文件第一行包含三个整数,分别表示输入的个数,门的个数,连接到输出的门的编号。以下的m行描述网络中的连接情况。第I行表示第I个门的两个输入,两个输 入为范围[-n,m]之间的一个整数。如果输入是网络的第k个输入,则连接的描述是一个整数-k,如果输入是第j个门,则连接的描述是一个整数j。以下两 行各有一个n位二进制串,表示输入的上限和下限。我们假设给定范围内最多100000种输入。

输出格式: 输出文件包含一个整数,表示给定范围内有多少种输入可以使输出为1。

样例:

输入文件xor.in:

5 6 5
-1 -2
1 3
1 -2
2 -3
4 6
-4 -5
00111
01110

输出文件xor.out

5