QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#844608 | #3472. EvenOdd | AlicX | AC ✓ | 0ms | 3904kb | C++20 | 3.8kb | 2025-01-06 08:57:35 | 2025-01-06 08:57:40 |
Judging History
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'