题目相关
题目链接:Ryoku 与最初之人笔记
题目背景:
Ryoku 在阅读「最初之人」的笔记的时候,发现了一个有趣的运算:$xor$,这个运算的输入是两个数,输出是一个数,对应的运算时将输入的两个数化为二进制,再把每一位进行比较,若相同则输出的二进制中的这一位为 $0$,否则为 $1$。
在关于运算 $xor$ 笔记的下面有一道习题。Ryoku 很快就得出了答案,她想要考考你。
题目描述:
Ryoku 向你复述了题目:求:
$$\sum_{a = 0}^n \sum_{b = a + 1}^n [a\equiv b\pmod {a \text{ xor } b}]$$
即:求满足 $a\equiv b\pmod {a \text{ xor } b}$,且 $a,b$ 均为小于等于 $n$ 的非负整数,$a<b$,的有序二元组 $(a,b)$ 个数。
输入输出格式:
输入格式:
输入包含一个整数 $n$。
输出格式:
输出包含一个整数,为上式的值,答案对 $10^9 + 7$ 取模。
输入输出样例:
输入 | 输出 | |
---|---|---|
#1 | 2 | 2 |
#2 | 42 | 274 |
说明:
样例解释:
样例1:$(0,1), (0,2)$
数据范围:
对于 $20$% 的数据,$n\le 10^3$。
对于 $60$% 的数据,$n\le 10^6$。
对于 $70$% 的数据,$n\le 10^9$。
对于 $100$% 的数据,$2\le n \le 10^{18}$。
博主乱搞
蒟蒻解析:
转化一下,这道题就让我们找有多少组 $(a,b)$ 满足 $b-a$ 是 $a\ xor\ b$ 的倍数。
我们要事先了解一个非常重要的结论:$a-b≤a\ xor\ b$。证明如下:
我们将两个数二进制拆开,即$a=\sum\limits_{k=0}{a_k{2^k}},b=\sum\limits_{k=0}{b_k{2^k}}$,$c=a\ xor\ b$ 也是如此。我们考虑每一位情况:
$$a_k=1,b_k=1\Rightarrow a_k-b_k=0,c_k=0\Rightarrow a_k-b_k=c_k$$
$$a_k=1,b_k=0\Rightarrow a_k-b_k=1,c_k=1\Rightarrow a_k-b_k=c_k$$
$$a_k=0,b_k=1\Rightarrow a_k-b_k=-1,c_k=1\Rightarrow a_k-b_k<c_k$$
$$a_k=0,b_k=0\Rightarrow a_k-b_k=0,c_k=0\Rightarrow a_k-b_k=c_k$$
每一位保证$a_k-b_k≤c_k$,总体也可得到。因为 $a,b$ 题目要求不等,所以题目转化为求有多少组 $a,b$ 满足 $b-a=a\ xor\ b$。
我们再次把问题拆开来看:对于每一位,为了确保两边相等,只有以下方案:$a_k=1,b_k=1;a_k=0,b_k=1;a_k=0,b_k=0$。然后我们利用数位dp的方法乱搞即可。
蒟蒻代码:
1 |
|