ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214650 | #2477. 狸猫的数 | N | 30 | 88ms | 41536kb | C++11 | 2.0kb | 2024-11-20 22:40:28 | 2024-11-20 23:11:31 |
answer
//
// na 2477-real.cpp
// Competitive Programming
//
// Created by m2 on 2024/11/20.
//
#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long int ll;
const int maxn = 1e7 + 5;
const int mod = 998244353, inv2 = 499122177;
//namespace map{
//const int mem = 0xfffff;
//struct Node{
// int val;
// Node *nxt;
// Node(int val): val(val), nxt(nullptr) {}
// Node(){}
//};
//Node* head[mem];
//int que[mem], ql;
//int h(unsigned x){
// x ^= x << 13;
// x ^= x >> 17;
// return (x ^ (x << 5)) & mem;
//}
//inline void insert(int key){
// int pos = h(key);
// if(head[pos] == nullptr){
// que[ql++] = pos;
// head[pos] = new Node(key);
// }else{
// Node* ptr = head[pos];
// while(ptr->nxt != nullptr)
// ptr = ptr->nxt;
// ptr->nxt = new Node(key);
// }
//}
//inline bool found(int key){
// int pos = h(key);
// if(head[pos] == nullptr)
// return false;
// Node* ptr = head[pos];
// do{
// if(ptr->val == key)
// return true;
// ptr = ptr->nxt;
// }while(ptr != nullptr);
// return false;
//}
//inline void clear(){
// Node *ptr, *tmp;
// for(int i = 0; i < ql; ++i){
// ptr = head[que[i]];
// while(ptr != nullptr){
// tmp = ptr;
// ptr = ptr->nxt;
// delete tmp;
// }
// head[que[i]] = nullptr;
// }
// ql = 0;
//}
//}
#define lowbit(x) (x & -x)
int f[maxn + 1];
bool vis[maxn + 1];
int sol(int idx){
if(vis[idx])
return f[idx];
vis[idx] = true;
return f[idx] = ((sol(idx - lowbit(idx)) + sol(idx + lowbit(idx))) * ll(inv2) + 1) % mod;
}
int main(){
cin.tie(0)->sync_with_stdio(false);
int l, r;
cin >> l >> r;
for(int i = 1; (i >> 1) < r; i <<= 1){
f[i] = 2;
vis[i] = true;
}
int ans = 0;
for(int i = l; i <= r; ++i)
ans = (ans + sol(i)) % mod;
cout << ans << endl;
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1252kb
input:
2 20
output:
249561151
result:
ok single line: '249561151'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1256kb
input:
2 99
output:
62390703
result:
ok single line: '62390703'
Test #3:
score: 0
Runtime Error
input:
2 10000000
output:
result:
Test #4:
score: 0
Runtime Error
input:
6224 9999999
output:
result:
Test #5:
score: 10
Accepted
time: 88ms
memory: 41536kb
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