[ABC129E] Sum Equals Xor
阅读原文时间:2023年08月22日阅读:2

2023-01-15

题目传送门

翻译

难度&重要性(1~10):4

题目来源

AtCoder

dp/模拟

我们都知道,异或是一种不进位的加法,而要想 $ a + b = a \oplus b $ 就不能进位,也就是说每一位不能是 $ ( 1,1 ) $ 就有 $ ( 0,1 ),( 1,0 ),( 0,0 )$ 三种可能。

举例: $ 10 ,11 $ 是不可行的,因为它会进位,而 $ 100,010 $ 就可以。

然后,我们需要让它满足 $ a+b \le L $ 即 $ a \oplus b \le L $ 而我们都知道,比较两个数的大小,是从高位往低位比较的。所以我们只需要保证 $ a \oplus b $ 中第 \(k\) 位小于 \(L\) 前面的一样,后面的位数可以随便填,其方案数为 \(3^{k}\)。因为异或 \(1\) 有两种方案 $ ( 0,1 ),( 1,0 ) $ 所以前面部分方案数为 $ 2^{n-k-1} $。

已完成