QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#125225 | #6741. Digit | hos_lyric | AC ✓ | 747ms | 18536kb | C++14 | 6.0kb | 2023-07-16 07:51:07 | 2023-07-16 07:51:10 |
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 <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