自动搬运

查看原文

来自洛谷，原作者为

	Leianha 万般皆下品，惟有透彻高

搬运于2025-08-24 22:00:35，当前版本为作者最后更新于2019-10-02 12:21:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

高精度&找规律

今天模拟赛第一题，结果被狂虐。 很明显的打表找规律的题。（数位DP？不存在的）我们珂以用我们的暴力程序来观察一下。我们设f（x）为二进制数x经过一系类变换后得到的结果，就会发现f(i)是成片分布的。

举个栗子：

0000--->1

0001--->0

0010--->0

0011--->0

0100--->1

0101--->1

......

我们还可以发现后面相同的f(i)的长度为$2^k$（k不定），所以我们就能够在$O(len)$的时间复杂度内得到 f（i）为1的个数。又因为当n奇偶性不同的时候f答案也不相同，分别考虑一下就珂以啦。

gj work(gj x)
{
	if(x<gj(4))return gj(1);
	gj l=gj(4) , r=Min(x,gj(7)) , res=gj(1);int opt=1;
	for( ; ;l=r+gj(1) , r=Min(r*gj(2)+gj(1),x) , opt^=1)
	{
		if(opt)res=res+(r-l+gj(1));
		if(r==x)break;
	}
	return res;
}

另外因为答案特别大，所以我们需要写高精度，并且还要转化为为二进制。

void shuchu(gj x)
{
	if(!x.len)return (void)printf("0");
	gj lin=gj(1);
	while(lin<=x)lin=lin*gj(2);
	lin=lin/2;
	for(;;lin=lin/2)
	{
		if(lin<=x)
		{
			printf("1");
			x=x-lin;
		}
		else printf("0");
		if(lin==gj(1))break;
	}
}

最后献上我丑陋的代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int T,n,Q,ans;
char ch[205];
struct gj
{
    int len;
    int v[1000];
    gj(){len=0;memset(v,0,sizeof(v));}
    gj(int x)
    {
        len=0;memset(v,0,sizeof(v));
        while(x)
        {
            v[++len]=x%10;
            x/=10;
        }
    }
    friend bool operator <(const gj &a,const gj &b)
    {
        if(a.len<b.len)return 1;
        if(a.len>b.len)return 0;
        for(int i=a.len;i>=1;--i)
        {
            if(a.v[i]<b.v[i])return 1;
            if(a.v[i]>b.v[i])return 0;
        }
        return 0;
    }
    friend bool operator ==(const gj &a,const gj &b)
    {
        if(a.len!=b.len)return 0;
        for(int i=a.len;i>=1;--i)
        {
            if(a.v[i]!=b.v[i])return 0;
        }
        return 1;
    }
    friend bool operator <=(const gj &a,const gj &b)
    {
        if(a<b)return 1;
        else if(a==b)return 1;
        else return 0;
    }
    friend bool operator !=(const gj &a,const gj &b)
    {
        if(a.len!=b.len)return 1;
        for(int i=a.len;i>=1;--i)
        {
            if(a.v[i]!=b.v[i])return 1;
        }
        return 0;
    }
}x,y,res;
gj operator +(gj a,gj b)
{
    int len=a.len+b.len;
    gj c;
    c.len=len;
    for(int i=1;i<=len;++i)c.v[i]=a.v[i]+b.v[i];
    for(int i=1;i<=len;++i)
    {
        if(c.v[i]>=10)
        {
            ++c.v[i+1];
            c.v[i]-=10;
        }
    }
    while(c.len&&!c.v[c.len])c.len--;
    return c;
}
gj operator -(gj a,gj b)
{
    int len=max(a.len,b.len);
    gj c;
    for(int i=1;i<=len;++i)c.v[i]=a.v[i]-b.v[i];
    c.len=len;
    for(int i=1;i<=c.len;++i)
    {
        if(c.v[i]<0)
        {
            c.v[i+1]--;
            c.v[i]+=10;
        }
    }
    while(c.len&&!c.v[c.len])c.len--;
    return c;
}
gj operator *(gj a,gj b)
{
    gj c;
    for(int i=1;i<=a.len;++i)
    for(int j=1;j<=b.len;++j)
    c.v[i+j-1]+=a.v[i]*b.v[j];
    c.len=a.len+b.len;
    for(int i=1;i<=c.len-1;++i)
    {
        if(c.v[i]>=10)
        {
            c.v[i+1]+=c.v[i]/10;
            c.v[i]%=10;
        }
    }
    while(c.v[c.len]==0&&c.len>1)--c.len;
    return c;
}
gj operator /(gj a,long long b)
{
    gj c;int d=0;
    for(int i=a.len;i>=1;--i)
    c.v[++c.len]=((d*10+a.v[i])/b),d=(d*10+a.v[i])%b;
    for(int i=1;i<=c.len/2;++i)swap(c.v[i],c.v[c.len-i+1]);
    while(c.v[c.len]==0&&c.len>1)--c.len;
    return c;
}
ostream& operator << (ostream &out,const gj &a) 
{
    if(!a.len)
    {
        cout<<"0";
        return out;
    }
    for(int i=a.len;i>=1;i--)printf("%d",a.v[i]);
    return out;
}
gj Min(gj a,gj b)
{
	if(a<b)return a;
	else return b;
}
gj work(gj x)
{
	if(x<gj(4))return gj(1);
	gj l=gj(4) , r=Min(x,gj(7)) , res=gj(1);int opt=1;
	for( ; ;l=r+gj(1) , r=Min(r*gj(2)+gj(1),x) , opt^=1)
	{
		if(opt)res=res+(r-l+gj(1));
		if(r==x)break;
	}
	return res;
}
void shuchu(gj x)
{
	if(!x.len)return (void)printf("0");
	gj lin=gj(1);
	while(lin<=x)lin=lin*gj(2);
	lin=lin/2;
	for(;;lin=lin/2)
	{
		if(lin<=x)
		{
			printf("1");
			x=x-lin;
		}
		else printf("0");
		if(lin==gj(1))break;
	}
}
void slove2()
{
	x=y=res=gj(0);
	scanf("%s",ch+1);
	for(int i=1;i<=n;++i)
	{
		x=x*2+gj(ch[i]-'0');
	}
	scanf("%s",ch+1);
	for(int i=1;i<=n;++i)
	{
		y=y*2+gj(ch[i]-'0');
	}
	res=work(y)-work(x-gj(1));
	if((n&1)==(Q&1))res=y-x+1-res;
	shuchu(res);puts("");
}
int main()
{
	cin>>T;
	while(T--)
	{
		scanf("%d%d",&n,&Q);
		slove2();
	}
	fclose(stdin);fclose(stdout);
	return 0;
}