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} $。
已完成
手机扫一扫
移动阅读更方便
你可能感兴趣的文章