QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#125225#6741. Digithos_lyricAC ✓747ms18536kbC++146.0kb2023-07-16 07:51:072023-07-16 07:51:10

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-16 07:51:10]
  • 评测
  • 测评结果:AC
  • 用时:747ms
  • 内存:18536kb
  • [2023-07-16 07:51:07]
  • 提交

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 <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; }


////////////////////////////////////////////////////////////////////////////////
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>;

constexpr int LIM_INV = 110;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];

void prepare() {
  inv[1] = 1;
  for (int i = 2; i < LIM_INV; ++i) {
    inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
  }
  fac[0] = invFac[0] = 1;
  for (int i = 1; i < LIM_INV; ++i) {
    fac[i] = fac[i - 1] * i;
    invFac[i] = invFac[i - 1] * inv[i];
  }
}
Mint binom(Int n, Int k) {
  if (n < 0) {
    if (k >= 0) {
      return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);
    } else if (n - k >= 0) {
      return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);
    } else {
      return 0;
    }
  } else {
    if (0 <= k && k <= n) {
      assert(n < LIM_INV);
      return fac[n] * invFac[k] * invFac[n - k];
    } else {
      return 0;
    }
  }
}


unsigned long long S, T;

int mem[70][50][40];
Mint dp[70][50][40][30];

int counter;
Mint calc(int e2, int e3, int e5, int e7, unsigned long long x) {
  if (x > T) return 0;
  Mint &ret = dp[e2][e3][e5][e7];
  if (!(mem[e2][e3][e5] & 1 << e7)) {
    
    int tot = 0;
    int cnt[10] = {};
    for (unsigned long long xx = x; xx; ) {
      ++tot;
      ++cnt[xx % 10];
      xx /= 10;
    }
    ret = 0;
    for (int d = 1; d <= 9; ++d) if (cnt[d]) {
      int f2 = e2;
      int f3 = e3;
      int f5 = e5;
      int f7 = e7;
      switch (d + 1) {
        case 2: f2 += 1; break;
        case 3: f3 += 1; break;
        case 4: f2 += 2; break;
        case 5: f5 += 1; break;
        case 6: f2 += 1; f3 += 1; break;
        case 7: f7 += 1; break;
        case 8: f2 += 3; break;
        case 9: f3 += 2; break;
        case 10: f2 += 1; f5 += 1; break;
        default: assert(false);
      }
      const Mint res = calc(f2, f3, f5, f7, x * (d + 1));
      ret += cnt[d] * res;
    }
    ret += tot;
    ret *= inv[tot - cnt[0]];
// cerr<<e2<<" "<<e3<<" "<<e5<<" "<<e7<<" "<<x<<": "<<ret<<endl;
    
    mem[e2][e3][e5] |= 1 << e7;
++counter;
  }
  return ret;
}

int main() {
  prepare();
  
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%llu%llu", &S, &T);
    
    memset(mem, 0, sizeof(mem));
    const Mint ans = calc(0, 0, 0, 0, S);
    printf("%u\n", ans.x);
#ifdef LOCAL
cerr<<"counter = "<<counter<<endl;
#endif
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4164kb

input:

3
1 10
1 100
1 1000

output:

3
4
942786340

result:

ok 3 number(s): "3 4 942786340"

Test #2:

score: 0
Accepted
time: 487ms
memory: 17024kb

input:

200
6093 473302679260560320
8548 407261659389622784
643 187875386337017408
8115 804844129595563776
3331 457909423622471360
8554 769878068775393152
2189 248771553604839360
7395 486014798136226944
8022 834223266052054400
9218 291007794161740672
8431 738787973811775616
1829 183591119896739584
816 23406...

output:

401752224
25564055
349247348
24571488
454552241
293307892
841921314
316896313
340265070
679232017
880794571
220757927
783764236
593413719
368463075
771186516
780654585
3628414
827863355
617858224
868927625
446978548
351494058
130284374
125073939
38120850
748432314
277667083
183850680
235708406
51111...

result:

ok 200 numbers

Test #3:

score: 0
Accepted
time: 80ms
memory: 18536kb

input:

200
3043059018339257 22277869996577613
9995869516 503712331451
389592 72563932968
3520234478258 476959582208156
77586585 711120211545804458
77846354 2243822883730937
9937954107 8390895135555
39032 603567
7739 4682236745217490
12277973519 7136059697857236
7264388 607094625
66205992799 4030219735546
3...

output:

108920162
651706276
549514920
440563412
796578996
851857830
191543780
540715694
549223125
380090491
553492005
247956062
582309209
67430878
174114881
1
669072219
981051601
561639793
304668111
397423058
607062211
8458982
479445466
287831358
913943402
533482140
801644611
519995972
239199505
587671914
2...

result:

ok 200 numbers

Test #4:

score: 0
Accepted
time: 718ms
memory: 17404kb

input:

200
58 999999999999997440
75 999999999999999872
52 999999999999997696
85 999999999999999360
12 999999999999999488
77 999999999999999232
80 999999999999999232
36 999999999999997184
51 999999999999998720
79 999999999999997440
76 999999999999998592
90 999999999999997696
32 999999999999998336
67 9999999...

output:

603520497
574767370
222266238
241598642
627473669
958322466
776467011
836867165
317725053
772230956
80008248
170
205889745
956913345
252066713
183389093
251365357
387390363
836867165
660512518
265265911
574767370
317725053
620530996
15655429
247241569
103698881
940321220
960908253
960908253
66051251...

result:

ok 200 numbers

Test #5:

score: 0
Accepted
time: 226ms
memory: 17360kb

input:

200
509411 999999999999999232
33801448 999999999999998720
65 999999999999998208
6 999999999999997184
404287 999999999999999360
800418816395 999999999999999232
44589090134507 999999999999997312
2008080 999999999999999360
13 999999999999998976
87 999999999999999872
206327851576605 999999999999999744
3...

output:

883813861
221710219
620530996
252066714
168038945
932330901
77414612
443356611
1883978
608670663
568648025
891202485
151357997
793825022
180372901
749235099
391331669
890726608
103698881
258627374
738512765
18273750
771644777
916674174
110687232
890972839
85823452
799141196
739829892
675630993
44879...

result:

ok 200 numbers

Test #6:

score: 0
Accepted
time: 747ms
memory: 16952kb

input:

200
1 1000000000000000000
1 1000000000000000000
1 1000000000000000000
1 1000000000000000000
1 1000000000000000000
1 1000000000000000000
1 1000000000000000000
1 1000000000000000000
1 1000000000000000000
1 1000000000000000000
1 1000000000000000000
1 1000000000000000000
1 1000000000000000000
1 10000000...

output:

252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
252066716
...

result:

ok 200 numbers