2019.01.23【NOIP提高组】模拟赛A&B组 JZOJ 3084 超级变变变

$Description$Description

定义一种函数
$f(x)=x-1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [x\ mod\ 2=1]\\ f(x)=\frac x2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [x\ mod\ 2=0]$f(x)=x−1                       [x mod 2=1]f(x)=2x​                            [x mod 2=0]
给定$k$k，求出$[L\sim R]$[L∼R]中能够通过$f(x)$f(x)转移过来的个数

对于50%的数据，$0&lt;=k,A,B&lt;=10^6$0<=k,A,B<=106

对于100%的数据，$0&lt;=k,A,B&lt;=10^{18} ,A&lt;=B$0<=k,A,B<=1018,A<=B

---

$Solution$Solution

把式子倒过来，发现

$x-&gt;2x$x−>2x

$x-&gt;2x+1$x−>2x+1

也就是说，$k$k能够转换成$2k$2k以及$2k+1$2k+1，于是设$solve(x)$solve(x)表示前$x$x个数中能转移成$k$k的个数，则我们发现这能够转移的个数形成了一颗二叉树，如图

我们发现，$k​$k​能转换到的节点个数即为以$k​$k​为根的二叉树中$X​$X​的位置前的所有节点的个数，倍增找$x​$x​即可，时间复杂度$O(loga+logb)​$O(loga+logb)​

---

$Code$Code

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
LL power[63],k,a,b,ans;
inline char Getchar()
{
    static char buf[1000000],*p1=buf+1000000,*pend=buf+1000000;
    if(p1==pend)
	{
        p1=buf; pend=buf+fread(buf,1,1000000,stdin);
        if (pend==p1) return -1;
    }
    return *p1++;
}
inline LL read()
{
	char c;int d=1;LL f=0;
	while(c=Getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=Getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
inline void write(register LL x)
{
	if(x<0)putchar(45),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
	return;
}
inline LL solve(LL x)
{
	if(!k) return x;
	if(k==1) return x;//两个特判
	if(k&1)//如果k是奇数，那么就是由k组成的二叉树
	{
		LL now=0,i=1;
		if(x>=k) now++;
		for(i=1;k*power[i]<=x;i++) now+=min(power[i],x-k*power[i]+1);//计算x是否为这层的叶子节点，是的话加上这层叶子编号不大于x的个数，不是的话直接加上整一层
		return now;
	}
	LL now=0,i=0;//如果k是偶数，则此时根有可能是k+1，所以层数要往下移一层
	if(x>=k) now++;if(x>=k+1) now++;
	for(i=1;k*power[i]<=x;i++) now+=min(power[i+1],x-k*power[i]+1);//同上
	return now;
}
signed main()
{
	power[0]=1;
	for(register int i=1;i<63;i++) power[i]=power[i-1]<<1;//预处理2的次幂
	k=read();a=read();b=read();
	write(solve(b)-solve(a-1));
}