ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214586 | #2477. 狸猫的数 | nodgd | 100 | 8ms | 1144kb | C++11 | 1.4kb | 2024-11-20 19:14:29 | 2024-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