QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#394746#1372. Rainbow NumbersKareemEssam#AC ✓103ms58700kbC++201.6kb2024-04-20 19:04:502024-04-20 19:04:50

Judging History

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

  • [2024-04-20 19:04:50]
  • 评测
  • 测评结果:AC
  • 用时:103ms
  • 内存:58700kb
  • [2024-04-20 19:04:50]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define ll long long
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long double ld;


#define lmao ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 1e5 + 5, M = 1e4 + 5, MOD = 998244353, LOG = 20, Msk = 21, pw1 = 31, pwe2 = 37;

string a, b;
ll mem[N][2][2][15];

ll solve(int idx, bool canDown, bool canExceed, int lst) {
    if (idx == b.size())
        return 1;
    ll &ret = mem[idx][canDown][canExceed][lst];
    if (~ret)
        return ret;
    
    ret = 0;
//    if (idx == 0 && a[idx] == '0') {
//        ret = solve(idx + 1, canDown, 1, lst);
//    }
    for (int d = 0; d < 10; d++) {
        if (d == lst)
            continue;
        if (!canDown && d < (a[idx] - '0'))
            continue;
        if (!canExceed && d > (b[idx] - '0'))
            continue;
        ret = ret % MOD + solve(idx + 1, canDown | (d > (a[idx] - '0')), canExceed | (d < (b[idx] - '0')), d) % MOD;
        ret %= MOD;
    }
    return ret;
}

void testCase() {
    cin >> a >> b;
    reverse(a.begin(), a.end());
    while (a.size() != b.size())
        a.push_back('0');
    reverse(a.begin(), a.end());
    memset(mem, -1, sizeof mem);
    cout << solve(0, 0, 0, 10);
}

signed main() {

    lmao
    int t = 1;
//    cin >> t;
    while (t--)
        testCase();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 50460kb

input:

3
65

output:

58

result:

ok single line: '58'

Test #2:

score: 0
Accepted
time: 0ms
memory: 50444kb

input:

37
524

output:

403

result:

ok single line: '403'

Test #3:

score: 0
Accepted
time: 0ms
memory: 50536kb

input:

974
9522

output:

6271

result:

ok single line: '6271'

Test #4:

score: 0
Accepted
time: 4ms
memory: 50460kb

input:

50518
71177

output:

13592

result:

ok single line: '13592'

Test #5:

score: 0
Accepted
time: 0ms
memory: 50584kb

input:

31718
829025

output:

477007

result:

ok single line: '477007'

Test #6:

score: 0
Accepted
time: 3ms
memory: 50608kb

input:

2673659
3522358

output:

444961

result:

ok single line: '444961'

Test #7:

score: 0
Accepted
time: 0ms
memory: 50592kb

input:

68790054
74835016

output:

3158763

result:

ok single line: '3158763'

Test #8:

score: 0
Accepted
time: 7ms
memory: 50664kb

input:

17596932
830146213

output:

355204747

result:

ok single line: '355204747'

Test #9:

score: 0
Accepted
time: 0ms
memory: 50596kb

input:

4559302681
8460113494

output:

551444164

result:

ok single line: '551444164'

Test #10:

score: 0
Accepted
time: 3ms
memory: 50528kb

input:

69096117055
78607961801

output:

325094872

result:

ok single line: '325094872'

Test #11:

score: 0
Accepted
time: 0ms
memory: 50596kb

input:

73724561911
889698372081

output:

41274511

result:

ok single line: '41274511'

Test #12:

score: 0
Accepted
time: 56ms
memory: 55332kb

input:

394508574650091022512909571921114492507182694804026914557940803351210811949294279029752773817948937368669076640956044457423812581727430884005816206959427698347341885326394187628757727906699306514383875164462186324492548299764354798393930933304229249368412800790454859889329435645073095955728789171702...

output:

756013076

result:

ok single line: '756013076'

Test #13:

score: 0
Accepted
time: 66ms
memory: 56572kb

input:

422014715369079097925608576097053393447341302972956361410316610182985064145389774113205524523087296205181295465843585593935732826938976987802078878325619776564276368817692500878159975485238243080947879152156568498810626499536300978108439515929336284446557185830049933423981614786282183661906272862517...

output:

910290565

result:

ok single line: '910290565'

Test #14:

score: 0
Accepted
time: 44ms
memory: 54824kb

input:

629396096057468187536008660523981385068079952319349471675185632997043167437177453007637825175211086119803071189551537498462585481009493935144671873254853670403033132984991648864417820658966727747779525379302774945537232349542662015587544507173985564040097599634973358738856506578728656284970453992909...

output:

206648751

result:

ok single line: '206648751'

Test #15:

score: 0
Accepted
time: 84ms
memory: 58328kb

input:

199626343357951152976038386589371212733444160365124954296963099284660388005029305337631801634925234172185609304248376473380083105406411526104699402946739597346435624847786625103712052504238131893994452042122278321653786103152589778095076110445791863192424539886648381508796263443067972336469068586450...

output:

718053737

result:

ok single line: '718053737'

Test #16:

score: 0
Accepted
time: 42ms
memory: 54896kb

input:

416808467195722010717127833402137108329359612596927289691425470111656493652261905429087663641343249238712155727095465434341074450710321551466047302616559139335310175711953306158251471371425473739854879886873588044584832688470163949674325274969568377528513249445556658110466623454653717769390783039308...

output:

182246952

result:

ok single line: '182246952'

Test #17:

score: 0
Accepted
time: 103ms
memory: 58700kb

input:

123343027257017651518445188954611335922116205762639210047994511861224460368751657727094916366693982441252856763608738504776743932824426227912514755331398286427843785571450458430865025310462426643461359293139384334713525243669047961510996307364053779014126345116040064878119666567405582997008526481779...

output:

635917051

result:

ok single line: '635917051'

Test #18:

score: 0
Accepted
time: 65ms
memory: 56192kb

input:

555447303587984935082102315240572317427032365494842712316690651708012590452140846568605875046914403037659471823547090546652528677148568592178117915826208879342008567398432355062521103014413587212424186325363147338980680164777568474515738920096377955187197462657654532855548271944324696377703605930926...

output:

609877234

result:

ok single line: '609877234'

Test #19:

score: 0
Accepted
time: 24ms
memory: 52732kb

input:

346936986726555509250989806448369042413425814612507036715378765301213065566598275883962847974103750963496684004841771015308222144469853044247988854848255290418003505127692437063318505453103279396876102565651692643033740443939691521078223172329110270567092570987328376283086698808515395858671126318600...

output:

140021677

result:

ok single line: '140021677'