[ABC138F] Coincidence
阅读原文时间:2023年08月22日阅读:2

2023-02-03

题目传送门

翻译

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

题目来源

AtCoder

数位dp

\(1.\) 当 \(2x\leq y\),有\(y-x>y\% x\);

\(2.\) 当 \(2x>y\),有\(y-x=y\% x\)。

\(3.\) \(y\oplus x\geq y-x\)。

于是:

\(2x\leq y\) 时,不存在 \(y\oplus x=y\% x\)。

所以 \(2x>y\),即 \(x\) 和 \(y\) 的位数相同,最高位同时为 \(1\)。

那么问题就转化成,求 \(y-x=y\oplus x\) 的 \((x,y)\) 的对数。

满足 \(y-x=y\oplus x\),那么 \(y\) 二进制下为 \(1\),\(x\) 为 \(0\) 或 \(1\),\(y\) 二进制下为 \(0\),\(x\) 必为 \(0\)。

考虑数位 \(dp\),这种类型的数位 \(dp\) 不像常规的数位 \(dp\) ,用 \(0\sim r\) 的答案减去 \(0\sim l-1\) 的答案。

我们考虑枚举哪一位为最高位,然后 \(dp_{i,x1,x2}\)表示前 \(i\) 位,数的大小有没有达到下界 \(L\),有没有达到上界 \(R\) 的方案数,转移时先枚举 \(y\),再枚举 \(x\)。

已完成

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章