UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214586#2477. 狸猫的数nodgd1008ms1144kbC++111.4kb2024-11-20 19:14:292024-11-20 23:02:05

answer

#include <bits/stdc++.h>

using namespace std;

const int BUFFER_SIZE = 1 << 20;
char rb[BUFFER_SIZE], *rp = rb, *rt = rb;
inline char read_char() {
    return rp == rt ? (rt = rb + fread(rb, 1, BUFFER_SIZE, stdin), rp = rb, *rp ++) : *rp ++;
}
inline int read_int() {
    int x = 0;
    char ch = read_char(), flag = 0;
    while (ch != '-' && (ch < '0' || ch > '9')) {
        ch = read_char();
    }
    if (ch == '-') {
        flag = 1;
        ch = read_char();
    }
    for (x = 0; ch >= '0' && ch <= '9'; ch = read_char()) {
        x = x * 10 + (ch - '0');
    }
    return flag ? -x : x;
}

using namespace std;

const int P = 998244353;
typedef long long i64;

int dfs(i64 x) {
    if (!(x & x - 1)) return 2;
    int res = dfs(x + (x & -x)) + dfs(x - (x & -x));
    res -= res >= P ? P : 0;
    res = res & 1 ? res + P >> 1 : res >> 1;
    return res + 1;
}
int work(int x) {
    if (!x) return 0;
    if (x & 1) {
        int res = dfs(x) + work(x - 1);
        res -= res >= P ? P : 0;
        return res;
    } else {
        int a = work(x >> 1) * 2;
        a -= a >= P ? P : 0;
        int b = dfs(x);
        b = b & 1 ? b + P >> 1 : b >> 1;
        a -= b, a += a < 0 ? P : 0;
        a += x >> 1, a -= a >= P ? P : 0;
        return a;
    }
}
int main() {
    int l = read_int(), r = read_int();
    int res = work(r) - work(l - 1);
    res += res < 0 ? P : 0;
    printf("%d\n", res);
    return 0;
}

详细

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

Test #1:

score: 10
Accepted
time: 0ms
memory: 1140kb

input:

2 20

output:

249561151

result:

ok single line: '249561151'

Test #2:

score: 10
Accepted
time: 0ms
memory: 1144kb

input:

2 99

output:

62390703

result:

ok single line: '62390703'

Test #3:

score: 10
Accepted
time: 0ms
memory: 1140kb

input:

2 10000000

output:

761228612

result:

ok single line: '761228612'

Test #4:

score: 10
Accepted
time: 0ms
memory: 1140kb

input:

6224 9999999

output:

364267526

result:

ok single line: '364267526'

Test #5:

score: 10
Accepted
time: 0ms
memory: 1140kb

input:

233 8244453

output:

766249426

result:

ok single line: '766249426'

Test #6:

score: 10
Accepted
time: 0ms
memory: 1140kb

input:

19260817 19260917

output:

499676660

result:

ok single line: '499676660'

Test #7:

score: 10
Accepted
time: 0ms
memory: 1140kb

input:

19260817 998244353

output:

256554686

result:

ok single line: '256554686'

Test #8:

score: 10
Accepted
time: 1ms
memory: 1140kb

input:

233 999244353

output:

627196619

result:

ok single line: '627196619'

Test #9:

score: 10
Accepted
time: 3ms
memory: 1140kb

input:

233 1000000007

output:

199422176

result:

ok single line: '199422176'

Test #10:

score: 10
Accepted
time: 4ms
memory: 1144kb

input:

1 2000000007

output:

25669823

result:

ok single line: '25669823'

Extra Test:

score: 0
Extra Test Passed