QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#382331 | #8565. Basic Blooms | hos_lyric | AC ✓ | 293ms | 11480kb | C++14 | 5.3kb | 2024-04-08 12:31:46 | 2024-04-08 12:31:46 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;
using Double = long double;
struct Entry {
Mint r;
// 2^k x
int k;
Double x;
// c...c in base b
int b, c, n;
Entry next() const {
Entry e = *this;
e.adv();
return e;
}
void adv() {
(r *= b) += c;
(x *= b) += pow(2.0, -k) * c;
for (; x >= 2.0; x /= 2.0) ++k;
++n;
}
bool operator<(const Entry &e) const {
return ((k != e.k) ? (k > e.k) : (x > e.x));
}
Double ratio(const Entry &e) const {
return pow(2.0L, e.k - k) * (e.x / x);
}
};
constexpr int B = 16;
constexpr int N = 1'000'005;
int main() {
priority_queue<Entry> que;
for (int b = 2; b <= B; ++b) {
for (int c = 1; c < b; ++c) {
que.push(Entry{0U, 0, 0.0L, b, c, 0});
}
}
vector<Mint> rs(N);
Double minRatio = 2.0L;
for (int i = 0; i < N; ++i) {
rs[i] = que.top().r;
vector<Entry> es;
for (; que.size() && rs[i] == que.top().r; que.pop()) es.push_back(que.top());
if (que.size()) chmin(minRatio, es[0].ratio(que.top()));
for (const Entry &e : es) que.push(e.next());
}
// cerr<<"rs = "<<rs<<endl;
fprintf(stderr,"minRatio = %.20Lf\n",minRatio);
vector<Mint> rsSum(N + 1, 0);
for (int i = 0; i < N; ++i) rsSum[i + 1] = rsSum[i] + rs[i];
for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
int L, R;
scanf("%d%d", &L, &R);
++R;
const Mint ans = rsSum[R] - rsSum[L];
printf("%u\n", ans.x);
}
#ifndef LOCAL
break;
#endif
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 137ms
memory: 11480kb
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: 143ms
memory: 11284kb
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: 293ms
memory: 11436kb
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