QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#844630 | #3472. EvenOdd | highkj | AC ✓ | 0ms | 3676kb | C++14 | 2.0kb | 2025-01-06 09:19:14 | 2025-01-06 09:19:14 |
Judging History
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
*/
Details
Tip: Click on the bar to expand more detailed information
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'