自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:16:44，当前版本为作者最后更新于2020-01-31 19:43:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一般情况下，看到 $\text{xor,and,or},+,-$ 等等毒瘤运算结合的时候，下面这个换元都会非常有效：

设 $y=a\;\text{and}\;b$，$a=x+y$，$b=y+z$，则 $a\;\text{or}\;b=x+y+z$，$a\;\text{xor}\;b=x+z$。

比如本题，采用以上换元，我们可以得到：$x+z|(y+z)-(x+y)$，即 $x+z|z-x$。

由于 $z+x\ge z-x>0$，所以 $x=0$，即 $a$ 的二进制位被 $b$ 的二进制位完全包含。

因此，我们枚举 $b$，对于每个 $b$，很显然有 $2^{f(b)}-1$ 个满足条件的 $a$，其中 $f(b)$ 表示 $b$ 在二进制下为 $1$ 的位的个数。

所以答案为 $\sum\limits_{i=1}^n(2^{f(i)})-n$。

记 $s(n)=\sum\limits_{i=1}^n2^{f(i)}$。

$f(n)$ 显然是可以 $O(\log n)$ 求的：（ll代表long long，后面同理）

inline ll f(ll n){if(!n)return 0;return f(n>>1)+n&1;}

即，$f(2n+1)=f(n)+1,f(2n)=f(n)$。

（代码中我使用了另一种实现方式）

由于我们有：

$$\begin{aligned}s(2n)&=\sum_{i=1}^{2n}2^{f(i)}\\&=\sum_{i=1}^n2^{f(2i-1)}+\sum_{i=1}^n2^{f(2i)}\\&=\sum_{i=1}^n2^{f(i-1)+1}+\sum_{i=1}^n2^{f(i)}\\&=2(1+\sum_{i=1}^{n-1}2^{f(i)})+\sum_{i=1}^n2^{f(i)}\\&=2+2s(n-1)+s(n)\\&=3s(n-1)+2^{f(n)}+2\end{aligned} $$

因此我们就可以递归/倍增求 $s(n)$ 了。最后减去 $n$ 即可。

$\texttt{code:}$

#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
	T f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
	x*=f;
	return x;
}
ll rd(){ll x;rd(x);return x;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;

const ll p=1000000007;
ll p2[70];
ll mod(ll t){return t>=p?t-p:t;}
int bitc(ll x){int ans=0;while(x)x&=x-1,++ans;return ans;}
ll f(ll n){return p2[bitc(n)];}
ll sum(ll n)
{
	if(n==0) return 0;
	if(n&1) return mod(sum(n^1)+f(n));
	ll t=sum((n>>1)-1);
	return (3*t+f(n>>1)+2)%p;
}
int main()
{
	p2[0]=1;F(i,1,64) p2[i]=mod(2*p2[i-1]);
	ll n;
	cin>>n;
	cout<<((sum(n)-n)%p+p)%p<<endl;
	return 0;
}