NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #214634 | #2477. 狸猫的数 | KXG | 50 | 316ms | 78636kb | C++11 | 692b | 2024-11-20 21:18:52 | 2024-11-20 23:07:52 |
answer
#include <cstdio>
using namespace std;
const long long mod = 998244353;
int lowbit(int i) {
return i & (-i);
}
int change(int i) {
return i / lowbit(i);
}
long long dp[10000010];
long long inv2 = (mod + 1) / 2;
int main() {
int l, r;
long long ans = 0;
scanf("%d%d", &l, &r);
dp[1] = 2;
for (int i = 2; i <= r; i++) {
if (lowbit(i) == 1) {
dp[i] = (dp[change(i + lowbit(i))] + dp[change(i - lowbit(i))]) * inv2 % mod + 1;
} else {
dp[i] = dp[change(i)];
}
}
for (int i = l; i <= r; i++) {
ans += dp[i];
ans %= mod;
}
printf("%lld\n", ans);
return 0;
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 512kb
input:
2 20
output:
249561151
result:
ok single line: '249561151'
Test #2:
score: 10
Accepted
time: 0ms
memory: 508kb
input:
2 99
output:
62390703
result:
ok single line: '62390703'
Test #3:
score: 10
Accepted
time: 122ms
memory: 78636kb
input:
2 10000000
output:
761228612
result:
ok single line: '761228612'
Test #4:
score: 10
Accepted
time: 105ms
memory: 78632kb
input:
6224 9999999
output:
364267526
result:
ok single line: '364267526'
Test #5:
score: 10
Accepted
time: 89ms
memory: 64916kb
input:
233 8244453
output:
766249426
result:
ok single line: '766249426'
Test #6:
score: 0
Runtime Error
input:
19260817 19260917
output:
result:
Test #7:
score: 0
Runtime Error
input:
19260817 998244353
output:
result:
Test #8:
score: 0
Runtime Error
input:
233 999244353
output:
result:
Test #9:
score: 0
Runtime Error
input:
233 1000000007
output:
result:
Test #10:
score: 0
Runtime Error
input:
1 2000000007
