QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#844860#3472. EvenOddCYYHAC ✓0ms3856kbC++141.9kb2025-01-06 11:44:332025-01-06 11:44:35

Judging History

This is the latest submission verdict.

  • [2025-01-06 11:44:35]
  • Judged
  • Verdict: AC
  • Time: 0ms
  • Memory: 3856kb
  • [2025-01-06 11:44:33]
  • Submitted

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'