QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#473181#8565. Basic Bloomsucup-team2307AC ✓1822ms9732kbC++202.3kb2024-07-11 22:50:522024-07-11 22:50:53

Judging History

你现在查看的是最新测评结果

  • [2024-07-11 22:50:53]
  • 评测
  • 测评结果:AC
  • 用时:1822ms
  • 内存:9732kb
  • [2024-07-11 22:50:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
//#define int ll
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back

const int MOD=998244353;

struct Big: vector<signed> {
    static const int BASE = MOD;
#define me (*this)
    Big() {}
    Big(auto val) { while (val) pb(val % BASE), val /= BASE; }
    auto get(int i) const { return i < sz(me) ? me[i] : 0; }
    auto operator<=>(const Big& oth) const {
        for (int i = max(sz(me), sz(oth)) - 1; i >= 0; i--)
            if (auto res = me.get(i) <=> oth.get(i); res != 0) return res;
        return 0 <=> 0;
    }
    Big& operator+=(const Big& oth) {
        for (int i = 0, r = 0; i < sz(oth) || r; i++) {
            if (i == size()) pb(0);
            me[i] += r + oth.get(i);
            if (r = me[i] >= BASE) me[i] -= BASE;
        }
        return me;
    }
    Big& operator*=(int oth) {
        for (int i = 0, r = 0; i < sz(me) || r; i++) {
            if (i == size()) pb(0);
            ll cur = me[i] * ll(oth) + r;
            me[i] = cur % BASE;
            r = cur / BASE;
        }
        return me;
    }
};

struct Seq
{
    int base,dig;
    Big num;
    Seq(int base,int dig):base(base),dig(dig),num{dig} {}
    void next()
    {
        num*=base;
        num+=dig;
    }
    friend bool operator<(const Seq&x,const Seq&y)
    {
        return x.num>y.num;
    }
};

const int N=1e6+100;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    priority_queue<Seq> pq;
    for(int base=2;base<=16;base++)
        for(int dig=1;dig<base;dig++)
            pq.emplace(base,dig);

    vector<int> nums{0};
    Big prv;
    while(nums.size()<=N)
    {
        Seq cur=pq.top();
        pq.pop();
        if(cur.num!=prv)
            prv=cur.num,
                    nums.pb({prv.front()});
        cur.next();
        pq.push(cur);
    }
    for(int i=1;i<sz(nums);i++)
        (nums[i]+=nums[i-1])%=MOD;
    int t;
    cin>>t;
    while(t--)
    {
        int l,r;
        cin>>l>>r;
        cout<<(nums[r]-nums[l-1]+MOD)%MOD<<"\n";
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1656ms
memory: 9732kb

input:

3
1 2
1 10
15 2000

output:

3
55
736374621

result:

ok 3 number(s): "3 55 736374621"

Test #2:

score: 0
Accepted
time: 1667ms
memory: 9528kb

input:

100000
26 99975
57 99944
28 99973
62 99939
71 99930
25 99976
53 99948
60 99941
73 99928
72 99929
30 99971
7 99994
3 99998
35 99966
73 99928
68 99933
83 99918
37 99964
63 99938
17 99984
34 99967
74 99927
6 99995
3 99998
23 99978
91 99910
39 99962
85 99916
82 99919
17 99984
61 99940
31 99970
44 99957
...

output:

957904590
358359691
31524403
519690359
208321031
477204717
835715447
186583689
847423322
760952087
25753603
241428916
832623523
232679133
847423322
11425904
640652773
663756612
767901835
356898792
503593019
495288401
265039242
832623523
793754988
389398856
758928836
349243444
158978749
356898792
873...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 1822ms
memory: 9264kb

input:

1000000
561662 731870
560627 798415
497930 613164
210084 556894
479283 902738
271881 288854
467622 971733
55854 157477
310152 415183
146385 874852
140599 526659
438420 629148
733746 924626
84146 436790
275793 457537
466464 541539
661070 696519
534866 688272
190259 412401
206392 354525
2344 217676
51...

output:

387682849
91353801
759238022
175113502
143631299
488887729
201615869
359127675
954541571
806609754
254074751
589282709
523407089
298821716
593042756
268635027
495659009
878948937
741148909
716887807
31798813
425888650
765930054
831198164
372500280
694558761
918178838
919393601
661100143
134966024
37...

result:

ok 1000000 numbers

Extra Test:

score: 0
Extra Test Passed