小慕在调试一批刚采购的逻辑门芯片时,发现其中某个或门模块存在异常:当用它计算两个二进制数的按位或时,第一个二进制数中会有两个发生随机,交换的位置完全随机,但只交换这两个位,其余位保持不变。 显然,这种交换可能会改变最终的或运算结果,也可能没有影响。 为了评估这个缺陷带来的影响并定位故障原因,小慕需要分析在所有可能的交换情况下,最终或结果发生变化的次数有多少种。
提示:带虚线的词点一下有通俗解释。
输入描述
第一行有一个正整数 N;其中 1≤N≤1000000。 第二行有一个长为 N 的二进制数,表示与电路的第一个输入数,即会发生比特交换的输入数。 第三行有一个长为 N 的二进制数,表示与电路的第二个输入数。注意第二个输入数不会发生比特交换。
输出描述
输出只有一个整数,表示会影响或结果的交换方案个数。
示例
示例 1
输入
6 011011 110110
输出
4
说明:原本 011011 和 110110 的或结果是 111111,但第一个输入数发生如下比特交换会影响最终计算结果: 1. 交换第 1 个比特和第 3 个比特,第一个输入数变为 110011,计算结果变为 110111 2. 交换第 1 个比特和第 6 个比特,第一个输入数变为 111010,计算结果变为 111110 3. 交换第 3 个比特和第 4 个比特,第一个输入数变为 010111,计算结果变为 110111 4. 交换第 4 个比特和第 6 个比特,第一个输入数变为 011110,计算结果变为 111110 其他的交换都不会影响计算结果,故输出 4。
示例 2
输入
3 010 110
输出
1
说明:原本 010 和 110 的或结果是 110,但第一个输入数可能会发生如下三种交换: 1. 交换第 1 个比特和第 2 个比特,第一个输入数变为 100,计算结果为 110,计算结果不变 2. 交换第 1 个比特和第 3 个比特,第一个输入数变为 010,计算结果为 110,计算结果不变 3. 交换第 2 个比特和第 3 个比特,第一个输入数变为 001,计算结果为 111,计算结果改变 故只有一种交换会改变计算结果。
时间限制 1000 ms · 内存限制 128 MB