题解 P6034 【Ryoku 与最初之人笔记】

· · 题解

一般情况下，看到 \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)}。

```cpp 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;
}