AlgoMooc
← 返回题库

P4001. 出错的或电路

中等通过率 55% · 提交 184 · 通过 102
位运算数学枚举

小慕在调试一批刚采购的逻辑门芯片时,发现其中某个或门模块存在异常:当用它计算两个二进制数的按位或时,第一个二进制数中会有两个发生随机,交换的位置完全随机,但只交换这两个位,其余位保持不变。 显然,这种交换可能会改变最终的或运算结果,也可能没有影响。 为了评估这个缺陷带来的影响并定位故障原因,小慕需要分析在所有可能的交换情况下,最终或结果发生变化的次数有多少种。

提示:带虚线的词点一下有通俗解释。

输入描述

第一行有一个正整数 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

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。