ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185834 | #2477. 狸猫的数 | snow_trace | 100 | 1ms | 1196kb | C++ | 2.0kb | 2023-09-30 11:27:57 | 2023-09-30 12:23:28 |
answer
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define endl '\n'
#define int long long
const int mod = 998244353;
int qp(int p,int q){
int ans = 1,pro = p;
while(q){
if(q&1)ans= ans*pro%mod;
pro = pro*pro%mod;q>>=1;
}return ans;
}int inv[35];
int val(int x){
if(x == 0)return 0;
if(x == 1)return 2;
int pos =0 ;
for(int i = 1;i<=31;i++){
if(x == ((int)1<<i))return 2;
if(x<((int)1<<i)){
pos = i;break;
}
}int p1 = ((int)1<<pos-1),p2 = (int)1<<pos,v1 = 2,v2 = 2;
while(1){
int mid = p1+p2>>1;
// cout<< x<<" "<<mid<<' '<<p1<<' '<<p2<<' '<<v1<<' '<<v2<<endl;
if(x == mid)return ((v1+v2)*inv[1]+1)%mod;
else if(x<mid)p2 = mid,v2 = (v1+v2)*inv[1]%mod+1;
else if(x>mid)p1 = mid,v1 = (v1+v2)*inv[1]%mod+1;;
}return 0;
}int ps(int x,int y){
return ((int)1<<x-1)+y-1;
}int pre(int dep,int pos){
// cout << dep << " " << pos << endl;
if(pos == 0)return 0;
if(dep == 1){
if(pos == 1)return 2;
if(pos == 2)return 4;
}if(pos%2){
return ((2*pre(dep-1,pos+1>>1)+pos/2-inv[1]*(2+val(ps(dep-1,pos+1>>1)))%mod)%mod+mod)%mod;
}else{
pos++;
return ((2*pre(dep-1,pos+1>>1)+pos/2-inv[1]*(2+val(ps(dep-1,pos+1>>1)))%mod-val(ps(dep,pos)))%mod+mod)%mod;
}
}
int solve(int x){
if(x <= 0)return 0;
if(x == 1)return 2;
if(x == 2)return 4;
if(x == 3)return 7;
if(x == 4)return 9;
int ans =4,p =4,pos,xx;
for(int i = 2;i<=x;i++){
/// cout << i << endl;
if(x>=((int)1<<i)){
xx = x-(1<<i);
p = (p*2+((int)1<<(i-2))-2)%mod;
// cout << p << endl;
ans = (ans+p-2)%mod;
pos =i+1;
}else break;
}//cout << pos << " " << ans << endl;
int pp = pre(pos,xx+1)-2;
return ((ans+pp+mod)%mod+mod)%mod;
}
signed main(){
for(int i =0;i<=30;i++)inv[i] = qp(1<<i,mod-2);
int l,r;cin >> l >> r;
int aa =solve(r),bb = solve(l-1);
// cout << bb << endl;
// cout<<aa<<" "<<bb<<endl;
// cout << 173*inv[2]%mod << endl;
cout << (aa-bb+mod)%mod;
// int x;cin >> x;
//cout << 17*inv[2]%mod << endl;
// cout << solve(x) << endl;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1196kb
input:
2 20
output:
249561151
result:
ok single line: '249561151'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1192kb
input:
2 99
output:
62390703
result:
ok single line: '62390703'
Test #3:
score: 10
Accepted
time: 0ms
memory: 1192kb
input:
2 10000000
output:
761228612
result:
ok single line: '761228612'
Test #4:
score: 10
Accepted
time: 0ms
memory: 1196kb
input:
6224 9999999
output:
364267526
result:
ok single line: '364267526'
Test #5:
score: 10
Accepted
time: 0ms
memory: 1196kb
input:
233 8244453
output:
766249426
result:
ok single line: '766249426'
Test #6:
score: 10
Accepted
time: 0ms
memory: 1196kb
input:
19260817 19260917
output:
499676660
result:
ok single line: '499676660'
Test #7:
score: 10
Accepted
time: 0ms
memory: 1192kb
input:
19260817 998244353
output:
256554686
result:
ok single line: '256554686'
Test #8:
score: 10
Accepted
time: 0ms
memory: 1196kb
input:
233 999244353
output:
627196619
result:
ok single line: '627196619'
Test #9:
score: 10
Accepted
time: 1ms
memory: 1192kb
input:
233 1000000007
output:
199422176
result:
ok single line: '199422176'
Test #10:
score: 10
Accepted
time: 0ms
memory: 1196kb
input:
1 2000000007
output:
25669823
result:
ok single line: '25669823'
Extra Test:
score: 0
Extra Test Passed