80>算法笔试模拟题精解之“Jerry 的异或运算”算法笔试模拟题精解之“Jerry 的异或运算”贡献者 | 猿圈简介：本题可以通过推导出一个公式来解答。题目描述等级：困难知识点：DP、数学查看题目：Jerry 的异或运算Jerry 最近在研究异或运算，异或也叫半加运算，其运算法则相当于不带进位的二进制加法。Jerry 给你一个数字 N，他想知道在 0 到 N 之间有多少对数字 (a,b) 满足 u+v=a,u ⊕ v = b, ⊕ 表示按位异或，由于答案将会非常大，请将结果对 1e9+7 取模。输入一个整数 N (0<=N<1e18)输出整数对 (a,b) 的数目，结果模 1e9+7示例 1输入：3输出：5算法笔试模拟题精解之“Jerry 的异或运算” <81解题方法：由于 u+v=a,u ⊕ v = b, 根据异或的性质我们可以知道：u+v = ((u&v)<<1) +(u ⊕ v)，所以 u+v >=u ⊕ v，那么只要 u+v<=n, u ⊕ v 也必定小于等于 n。于是这道题就转化成了对于 u+v<=n , 求 (u,v) 的对数。定 义 dp[n] 表 示 u+v<=n ,