UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#185834#2477. 狸猫的数snow_trace1001ms1196kbC++2.0kb2023-09-30 11:27:572023-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;
}

Details

小提示:点击横条可展开更详细的信息

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