QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#844608#3472. EvenOddAlicXAC ✓0ms3904kbC++203.8kb2025-01-06 08:57:352025-01-06 08:57:40

Judging History

This is the latest submission verdict.

  • [2025-01-06 08:57:40]
  • Judged
  • Verdict: AC
  • Time: 0ms
  • Memory: 3904kb
  • [2025-01-06 08:57:35]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int __int128
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
    il int read(){
        int x=0,f=1;char ch=gc;
        while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
        while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
        return x*f;
    }
    il int qmi(int a,int b,int p){
        int ans=1;
        while(b){
            if(b&1) ans=ans*a%p;
            a=a*a%p,b>>=1;
        }
        return ans;
    }
    il int gcd(int a,int b){
        if(!b) return a;
        return gcd(b,a%b);
    }
    il int lcm(int a,int b){
        return a/gcd(a,b)*b;
    }
    il void exgcd(int a,int b,int &x,int &y){
        if(!b) return x=1,y=0,void(0);
        exgcd(b,a%b,x,y);
        int t=x;
        x=y,y=t-a/b*x;
        return ;
    }
    il int F(int n,int a,int b,int c){
        //sum{|_ (ai+b)/c _| i:0~n}
        if(!n) return b/c;
        if(!a) return (n+1)*(b/c);
        if(a>=c||b>=c){
            int x=a/b,y=b/c;
            return n*(n+1)/2*x+(n+1)*y+F(n,a%c,b%c,c);
        }
        int m=(a*n+b)/c;
        return n*m+F(m-1,c,c-b+1,a);
    }
    struct lb{
        int d[64];
        il void print(){
            for(re int i=0;i<63;++i)
            if(d[i]) printf("%lld:%lld\n",i,d[i]);
            return ;
        }
        lb(){memset(d,0,sizeof(d));}
        il void operator +=(int x){
            for(re int i=62;i>=0;--i){
                if(!(x&(1ll<<i))) continue;
                if(d[i]) x^=d[i];
                else return d[i]=x,void(0);
            }
            return ;
        }
        int& operator [](int x){
            return d[x];
        }
        il void operator +=(lb &x){
            for(re int i=62;i>=0;--i)
            if(x[i]) *this+=x[i];
            return ;
        }
        il friend lb operator +(lb &x,lb &y){
            lb z=x;
            for(re int i=62;i>=0;--i)
            if(y[i]) z+=y[i];
            return z;
        }
        il int Max_calc(){
            int ans=0;
            for(re int i=62;i>=0;--i)
            if((ans^d[i])>ans) ans^=d[i];
            return ans;
        }
    };
    mt19937 rnd(time(0));
}
using namespace yzqwq;

const int p=1e9+7,N=64;
int f[N],__[N];

il int work(int x){
	int c=0;
	while(x>1){
//		++c;
//		x=(x+1)/2;
		x=(x+1)/2;
	}return c;
}

il void init(){
	f[0]=0,__[0]=1;
	for(re int i=1;i<N;++i) __[i]=__[i-1]*2,f[i]=(f[i-1]*2%p+qmi(2,i-1,p))%p;
	return ;
}
il int g(int x){
	int c=0;
	while(x>1){
		if(x%2==0) x/=2;
		else ++x,++c;
	}
	return c;
}
il int get(int l,int r){
	int sum=0,u=l;
	for(re int i=61;i>=0;--i){
		if(u+__[i]-1<=r){
			int L=u,R=u+__[i]-1,dep=0;
			while(L!=R){
				++dep;
				L=(L+1)/2,R=(R+1)/2;
			}
//			cout<<dep<<" ";
			int U=L;
			sum=(sum+f[dep])%p;
			L=u,R=u+__[i]-1;
			sum=(sum+(R-L+1)%p*g(U)%p)%p;
			u+=__[i];
		}
	}
	return sum;
}
il int work1(int x){
	int sum=0;
	for(re int i=0;i<=61;++i){
		int l=(1ll<<(i-1))+1,r=(1ll<<(i));
//		cout<<r<<" "<<x<<"\n";
		r=min(r,x);
		if(l>r) break;
		sum=(sum+i%p*((r-l+1)%p)%p)%p;
	}
	return sum;
}
il int work2(int x){
	int sum=0;
	if(x==1) return 0;
	for(re int i=0;i<=61;++i){
		int l=(1ll<<i)+1,r=(1ll<<(i+1));
		if(l>x) break;
		if(r<=x) sum=(sum+f[i])%p;
		else{
			r=min(r,x);
			sum=(sum+get(l,r))%p;
			break;
		}
	}
	return sum;
}

il void solve(){
	int l=rd,r=rd;
	init();
//	cout<<get(74);return ;
	int ans=(((work1(r)-work1(l-1)+work2(r)-work2(l-1))%p+p)%p+p)%p;
	cout<<(long long)ans;
    return ;
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    int t=1;while(t--)
    solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3648kb

input:

1 127

output:

1083

result:

ok single line: '1083'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

74 74

output:

11

result:

ok single line: '11'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

188481480076382025 735477894373585094

output:

603589184

result:

ok single line: '603589184'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

221018194823646727 598132723231895586

output:

593435414

result:

ok single line: '593435414'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

723254527395008082 857000792713570284

output:

130769773

result:

ok single line: '130769773'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

308610764995277671 886546357678103983

output:

981434297

result:

ok single line: '981434297'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

467129058436471616 929946560335162000

output:

956030241

result:

ok single line: '956030241'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

142308250729181166 793647580012269898

output:

890073540

result:

ok single line: '890073540'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

30010612464177072 225060844674934062

output:

192815207

result:

ok single line: '192815207'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

1 1

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

1 1000000000000000000

output:

826523937

result:

ok single line: '826523937'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

1 999999999999999999

output:

826523858

result:

ok single line: '826523858'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

4 16384

output:

311294

result:

ok single line: '311294'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

4398046511104 18014398509481984

output:

451815097

result:

ok single line: '451815097'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

4096 281474976710656

output:

231757660

result:

ok single line: '231757660'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

16 137438953472

output:

983959228

result:

ok single line: '983959228'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

8192 16777216

output:

570281997

result:

ok single line: '570281997'