QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382331#8565. Basic Bloomshos_lyricAC ✓293ms11480kbC++145.3kb2024-04-08 12:31:462024-04-08 12:31:46

Judging History

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

  • [2024-04-08 12:31:46]
  • 评测
  • 测评结果:AC
  • 用时:293ms
  • 内存:11480kb
  • [2024-04-08 12:31:46]
  • 提交

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