QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#473433 | #8565. Basic Blooms | ucup-team2307 | AC ✓ | 1740ms | 9752kb | C++20 | 2.2kb | 2024-07-12 03:35:59 | 2024-07-12 03:36:00 |
Judging History
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) { pb(val); }
auto operator<=>(const Big& oth) const {
if (auto res = sz(me) <=> sz(oth); res != 0) return res;
for (int i = sz(me) - 1; i >= 0; i--)
if (auto res = me[i] <=> oth[i]; res != 0) return res;
return 0 <=> 0;
}
Big &operator+=(const int &oth) {
for (int i = 0, r = oth; r; i++) {
if (i == size()) pb(0);
me[i] += r;
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: 1584ms
memory: 9224kb
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: 1598ms
memory: 9232kb
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: 1740ms
memory: 9752kb
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