avatar

目录
洛谷 P6034 Ryoku 与最初之人笔记

题目相关

题目链接: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的方法乱搞即可。

蒟蒻代码:

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
#define mod 1000000007
ll n;
ll ans;
int v[100],tot;
ll f[100][2][2];
ll dfs(int pos,ll val,int limit,int dif){
if (pos<0){
return (dif)?val:0;
}
if (f[pos][limit][dif]!=-1) return f[pos][limit][dif];
ll tmp=0;
int mx=(!limit)?1:v[pos];
if (mx==1){
tmp+=dfs(pos-1,val,limit,dif); //11
tmp+=dfs(pos-1,val,limit,1); //10
tmp+=dfs(pos-1,val,0,dif); //00
}else{
tmp+=dfs(pos-1,val,limit,dif); //00
}
tmp%=mod;
return f[pos][limit][dif]=tmp;
}
int main(){
memset(f,-1,sizeof(f));
scanf("%lld",&n);
ll tmp=n;
while (tmp){
if (tmp&1) v[tot]=1;
tot++; tmp>>=1;
}
cout<<dfs(tot-1,1,1,0)%mod;
return 0;
}
文章作者: lonlyn
文章链接: https://lonlyn.gitee.io/blog/2020/01/31/luoguP6034/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 lonlyn's blog

评论