QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#844860 | #3472. EvenOdd | CYYH | AC ✓ | 0ms | 3856kb | C++14 | 1.9kb | 2025-01-06 11:44:33 | 2025-01-06 11:44:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define il inline
#define ptc putchar
#define pb push_back
#define R(i, l, r) for (int i = l; i <= r; ++i)
#define debug puts("--------------------------------------------")
typedef long long ll;
typedef pair<int, int> PII;
namespace ZT {
template <typename T>
il void read(T &x) {
x = 0; T f = 1; char ch;
while (!isdigit(ch = getchar())) f -= (ch == '-') << 1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
x *= f;
}
template <typename T, typename ...L>
il void read(T &x, L &...y) {read(x); read(y...);}
template <typename T>
il void write(T x) {
if (x < 0) ptc('-'), x = -x;
if (x > 9) write(x / 10);
ptc(x % 10 + '0');
}
template <typename T, typename ...L>
il void write(T &x, L &...y) {write(x), ptc(' '); write(y...);}
}
using namespace ZT;
const int N = 2e5 + 5, P = 1e9 + 7;
#define int ll
int L, R;
int mlg(int x) {
int res = 0;
while (x != 1) {
x /= 2;
++res;
}
return res;
}
int lb(int x) {return x & -x;}
int len(int x) {return log2(x) + 1;}
int f(int x) {
int ct = __builtin_popcountll(x);
if (ct == 1) return mlg(x);
int t = lb(x);
return mlg(x) + 1 + (len(x) - ct - mlg(t) + 1);
}
int g(int x) {
if (x == 0 || x == 1) return 0;
if (x % 2 == 0) return (g(x / 2) * 2 % P + x / 2 * 3 % P - 2) % P;
else return (g(x - 1 >> 1ll) * 2 % P + (x - 1 >> 1ll) * 3 % P + f(x) - 2) % P;
}
signed main() {
cin >> L >> R;
// cout << g(11) - g(9) << endl;
// R(i, 1, 5) cout << f(i) << ' ' ; cout << endl;
// R(i, 1, 5) cout << g(i) << ' ' ; cout << endl;
// cout << f(10) << ' ' << f(11) << ' ' << f(12) << ' ' << f(13) << ' ' << f(14) << ' ' << f(15) << ' ' << f(16) << ' ' << f(17) << endl;
cout << (g(R) - g(L - 1) + P) % P << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
input:
1 127
output:
1083
result:
ok single line: '1083'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
74 74
output:
11
result:
ok single line: '11'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
188481480076382025 735477894373585094
output:
603589184
result:
ok single line: '603589184'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
221018194823646727 598132723231895586
output:
593435414
result:
ok single line: '593435414'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
723254527395008082 857000792713570284
output:
130769773
result:
ok single line: '130769773'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
308610764995277671 886546357678103983
output:
981434297
result:
ok single line: '981434297'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
467129058436471616 929946560335162000
output:
956030241
result:
ok single line: '956030241'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
142308250729181166 793647580012269898
output:
890073540
result:
ok single line: '890073540'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
30010612464177072 225060844674934062
output:
192815207
result:
ok single line: '192815207'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1 1
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
1 1000000000000000000
output:
826523937
result:
ok single line: '826523937'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
1 999999999999999999
output:
826523858
result:
ok single line: '826523858'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
4 16384
output:
311294
result:
ok single line: '311294'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
4398046511104 18014398509481984
output:
451815097
result:
ok single line: '451815097'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
4096 281474976710656
output:
231757660
result:
ok single line: '231757660'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
16 137438953472
output:
983959228
result:
ok single line: '983959228'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
8192 16777216
output:
570281997
result:
ok single line: '570281997'