UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214650#2477. 狸猫的数N3088ms41536kbC++112.0kb2024-11-20 22:40:282024-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

output:


result: