题解 CF1017B 【The Bits】

KEBrantily · 2021-08-23 09:45:00 · 题解

可以发现，若我们要得到一个新的 a 满足要求，必须要至少完成以下两种操作之一。

• 若在第 i 位上，a 为 1，b 为 0，那么将 a 这一位变为 0；

• 若在第 i 位上，a,b 均为 0，那么将 a 这一位变为 1。

我们设 a 有 x 个 1，y 个 0。再设有 z 个 a|b=0 的位置，k 个 a=1,b=0 的位置。

那么，将 a 中一个 0 填成 1 有 x 种方案，反过来为 y 种。

所以我们可以将上面操作的方案数算出，分别是 ky 和 zx。

又因为某些情况同时包含了这两种操作，会重复计算，所以要减去。

答案就是 ky+zx-kz。