QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#845300#3472. EvenOddyqrAC ✓0ms1592kbC++231.4kb2025-01-06 15:50:002025-01-06 15:50:01

Judging History

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

  • [2025-01-06 15:50:01]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:1592kb
  • [2025-01-06 15:50:00]
  • 提交

answer

#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
namespace IO {
	constexpr int bufsize = 230005;
	char buf[bufsize], *f1, *f2;
	char gtchar() {return f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++;}
	template<typename T> void read(T &ret)
	{
		int f = ret = 0;
		char ch = gtchar();
		while(!isdigit(ch)) f = ch == '-', ch = gtchar();
		while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = gtchar();
		if(f) ret = -ret;
	}
	template<typename T, typename ...t> void read(T &a, t &...b) {read(a), read(b...);}
}using IO::read;
typedef long long ll;
typedef unsigned long long ull;
constexpr int mod = 1e9 + 7;
ll l, r;
int f(ll x)
{
	int ret = 0;
	while(x > 1) ret += (x & 1) + 1, x = x + 1 >> 1;
	return ret;
}
// template<typename t> t Add(t a, t b) {return (a += b) >= mod? a - mod: a;}
int Add(int a, const int &b) {return (a += b) >= mod? a - mod: a;}
int solve(ll x)
{
	if(x <= 1) return 0;
	int ret = (x & 1)? f(x--): 0;
	ret = Add(Add(Add(ret, solve(x >> 1) * 2 % mod), (x >> 1) % mod * 3ll % mod), mod - 2);
	// if(ret < 0) printf("%lld %lld %lld\n", x, x + (x >> 1) - 2, solve(x >> 1)), exit(-1);
	return ret;
}
int main()
{
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	read(l, r);
	// printf("%lld\n", solve(l - 1));
	printf("%d\n", Add(solve(r), mod - solve(--l)));
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 127

output:

1083

result:

ok single line: '1083'

Test #2:

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

input:

74 74

output:

11

result:

ok single line: '11'

Test #3:

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

input:

188481480076382025 735477894373585094

output:

603589184

result:

ok single line: '603589184'

Test #4:

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

input:

221018194823646727 598132723231895586

output:

593435414

result:

ok single line: '593435414'

Test #5:

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

input:

723254527395008082 857000792713570284

output:

130769773

result:

ok single line: '130769773'

Test #6:

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

input:

308610764995277671 886546357678103983

output:

981434297

result:

ok single line: '981434297'

Test #7:

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

input:

467129058436471616 929946560335162000

output:

956030241

result:

ok single line: '956030241'

Test #8:

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

input:

142308250729181166 793647580012269898

output:

890073540

result:

ok single line: '890073540'

Test #9:

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

input:

30010612464177072 225060844674934062

output:

192815207

result:

ok single line: '192815207'

Test #10:

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

input:

1 1

output:

0

result:

ok single line: '0'

Test #11:

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

input:

1 1000000000000000000

output:

826523937

result:

ok single line: '826523937'

Test #12:

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

input:

1 999999999999999999

output:

826523858

result:

ok single line: '826523858'

Test #13:

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

input:

4 16384

output:

311294

result:

ok single line: '311294'

Test #14:

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

input:

4398046511104 18014398509481984

output:

451815097

result:

ok single line: '451815097'

Test #15:

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

input:

4096 281474976710656

output:

231757660

result:

ok single line: '231757660'

Test #16:

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

input:

16 137438953472

output:

983959228

result:

ok single line: '983959228'

Test #17:

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

input:

8192 16777216

output:

570281997

result:

ok single line: '570281997'