QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#844630#3472. EvenOddhighkjAC ✓0ms3676kbC++142.0kb2025-01-06 09:19:142025-01-06 09:19:14

Judging History

你现在查看的是最新测评结果

  • [2025-01-06 09:19:14]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3676kb
  • [2025-01-06 09:19:14]
  • 提交

answer

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int __int128
#define fire signed
#define il inline
template<class T> il void print(T x) {
	if(x<0) printf("-"),x=-x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
int T=1;
int l,r;
const int mod=1e9+7;
int qmi(int x,int y) {
	if(y<0) return false;
	int res=1;
	while(y) {
		if(y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}return res;
}
int f[100];
int jump(int x,int k) {
	while(k) {
		x=(x+1)/2;
		k--;
	}return x;
}
int get(int x) {
	int res=0;
	while(x!=1) {
		if(x&1) x++,res++;
		else x/=2;
	}return res;
}
int sum(int x) {
	int res=0;
	rep(i,0,61) {
		int l=(1ll<<i-1)+1,r=(1ll<<i);
		res+=max((int)0,min(r,x)-l+1)*i%mod;
		res%=mod;
	}return res;
}
int calc(int x) {
	if(x==1) return false;
	int res=0,san=0,now1=0,now2=0;
	rep(j,0,61) {
		f[j]=f[j-1]*2+qmi(2,j-1);
		int l=(1ll<<j)+1,r=(1ll<<j+1);
		r=min(r,x);
		if((r!=x)||(1ll<<j+1)-1==x) res+=f[j];
		else san=r-l+1,now1=l,now2=r;
		if(r==x) break;
	}
	if(san) {
		rep1(j,61,0) {
			int len=(1ll<<j);
			if(len<=san) {
				int now=jump(now1,j);
				res+=(get(now)*len%mod+f[j])%mod;
				res%=mod;
				san-=len;
				now1+=len;
			}
		}
	}
	return res;
}
void solve() {
	in(l),in(r);
//	cout<<(long long)jump(5,2)<<endl;
//	cout<<calc(5)+sum(5)<<endl;
	cout<<(long long)(((calc(r)-calc(l-1)+sum(r)-sum(l-1))%mod+mod)%mod);
//	print();
//	cout<<<<endl;
}
fire main() {
	while(T--) {
		solve();
	}
	return false;
}
/*
13 13
*/ 

详细

Test #1:

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

input:

1 127

output:

1083

result:

ok single line: '1083'

Test #2:

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

input:

74 74

output:

11

result:

ok single line: '11'

Test #3:

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

input:

188481480076382025 735477894373585094

output:

603589184

result:

ok single line: '603589184'

Test #4:

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

input:

221018194823646727 598132723231895586

output:

593435414

result:

ok single line: '593435414'

Test #5:

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

input:

723254527395008082 857000792713570284

output:

130769773

result:

ok single line: '130769773'

Test #6:

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

input:

308610764995277671 886546357678103983

output:

981434297

result:

ok single line: '981434297'

Test #7:

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

input:

467129058436471616 929946560335162000

output:

956030241

result:

ok single line: '956030241'

Test #8:

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

input:

142308250729181166 793647580012269898

output:

890073540

result:

ok single line: '890073540'

Test #9:

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

input:

30010612464177072 225060844674934062

output:

192815207

result:

ok single line: '192815207'

Test #10:

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

input:

1 1

output:

0

result:

ok single line: '0'

Test #11:

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

input:

1 1000000000000000000

output:

826523937

result:

ok single line: '826523937'

Test #12:

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

input:

1 999999999999999999

output:

826523858

result:

ok single line: '826523858'

Test #13:

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

input:

4 16384

output:

311294

result:

ok single line: '311294'

Test #14:

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

input:

4398046511104 18014398509481984

output:

451815097

result:

ok single line: '451815097'

Test #15:

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

input:

4096 281474976710656

output:

231757660

result:

ok single line: '231757660'

Test #16:

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

input:

16 137438953472

output:

983959228

result:

ok single line: '983959228'

Test #17:

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

input:

8192 16777216

output:

570281997

result:

ok single line: '570281997'