QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#759959#7954. Special NumbersSanguineChameleon#AC ✓423ms919532kbC++204.5kb2024-11-18 13:38:262024-11-18 13:38:27

Judging History

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

  • [2024-11-18 13:38:27]
  • 评测
  • 测评结果：AC
  • 用时：423ms
  • 内存：919532kb
查看
  • [2024-11-18 13:38:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

void justDoIt();

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    justDoIt();
    return 0;
}

const int MOD = 1e9 + 7;
const int K = 21;
const int MAX_C2 = K * 3;
const int MAX_C3 = K * 2;
const int MAX_C5 = K * 1;
const int MAX_C7 = K * 1;
const vector<int> PRIMES = {2, 3, 5, 7};
int a[K];
int cnt[10][4];
int need[4];
int dp[K + 1][2][2][2][MAX_C2 + 1][MAX_C3 + 1][MAX_C5 + 1][MAX_C7 + 1];
long long m;

// f1 - has the number started?
// f2 - is the number already smaller?
// f3 - does the number have a 0?

void add(int& var, int delta) {
    var += delta;
    if (var >= MOD) {
        var -= MOD;
    }
}

int calc(__int128 r) {
    for (int i = K - 1; i >= 0; i--) {
        a[i] = r % 10;
        r /= 10;
    }
    memset(dp, 0, sizeof(dp));
    dp[0][0][0][0][0][0][0][0] = 1;
    for (int i = 0; i < K; i++) {
        for (int f1 = 0; f1 < 2; f1++) {
            for (int f2 = 0; f2 < 2; f2++) {
                for (int f3 = 0; f3 < 2; f3++) {
                    for (int c2 = 0; c2 <= MAX_C2; c2++) {
                        for (int c3 = 0; c3 <= MAX_C3; c3++) {
                            for (int c5 = 0; c5 <= MAX_C5; c5++) {
                                for (int c7 = 0; c7 <= MAX_C7; c7++) {
                                    if (dp[i][f1][f2][f3][c2][c3][c5][c7] == 0) {
                                        continue;
                                    }
                                    for (int d = 0; d < 10; d++) {
                                        if (f2 == 0 && d > a[i]) {
                                            continue;
                                        }
                                        int ni = i + 1;
                                        int nf1 = f1 | (d != 0);
                                        int nf2 = f2 | (d < a[i]);
                                        int nf3 = f3 | (f1 && (d == 0));
                                        int nc2 = c2 + cnt[d][0];
                                        int nc3 = c3 + cnt[d][1];
                                        int nc5 = c5 + cnt[d][2];
                                        int nc7 = c7 + cnt[d][3];
                                        add(dp[ni][nf1][nf2][nf3][nc2][nc3][nc5][nc7], dp[i][f1][f2][f3][c2][c3][c5][c7]);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    int res = 0;
    for (int f1 = 1; f1 < 2; f1++) {
        for (int f2 = 0; f2 < 2; f2++) {
            for (int f3 = 0; f3 < 2; f3++) {
                for (int c2 = 0; c2 <= MAX_C2; c2++) {
                    for (int c3 = 0; c3 <= MAX_C3; c3++) {
                        for (int c5 = 0; c5 <= MAX_C5; c5++) {
                            for (int c7 = 0; c7 <= MAX_C7; c7++) {
                                int cur = dp[K][f1][f2][f3][c2][c3][c5][c7];
                                if (cur == 0) {
                                    continue;
                                }
                                if (f3 == 1) {
                                    add(res, cur);
                                }
                                else if (m == 1) {
                                    if (c2 >= need[0] && c3 >= need[1] && c5 >= need[2] && c7 >= need[3]) {
                                        add(res, cur);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return res;
}

__int128 toInt(string s) {
    __int128 res = 0;
    for (auto x: s) {
        res = res * 10 + (x - '0');
    }
    return res;
}

void justDoIt() {
    for (int d = 1; d < 10; d++) {
        for (int i = 0; i < 4; i++) {
            int p = PRIMES[i];
            int x = d;
            while (x % p == 0) {
                cnt[d][i]++;
                x /= p;
            }
        }
    }
    cin >> m;
    for (int i = 0; i < 4; i++) {
        int p = PRIMES[i];
        while (m % p == 0) {
            need[i]++;
            m /= p;
        }
    }
    string ls, rs;
    cin >> ls >> rs;
    __int128 l = toInt(ls);
    __int128 r = toInt(rs);
    int res1 = calc(l - 1);
    int res2 = calc(r);
    int res = (res2 + MOD - res1) % MOD;
    cout << res;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 363ms
memory: 919284kb

input:

5 1 20

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 358ms
memory: 919296kb

input:

5 50 100

output:

19

result:

ok single line: '19'

Test #3:

score: 0
Accepted
time: 369ms
memory: 919220kb

input:

15 11 19

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 339ms
memory: 919240kb

input:

1 100 100000

output:

99901

result:

ok single line: '99901'

Test #5:

score: 0
Accepted
time: 335ms
memory: 919532kb

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 344ms
memory: 919292kb

input:

10 800 43021

output:

23570

result:

ok single line: '23570'

Test #7:

score: 0
Accepted
time: 364ms
memory: 919272kb

input:

1125899906842624 1 100000000000000000000

output:

555058180

result:

ok single line: '555058180'

Test #8:

score: 0
Accepted
time: 368ms
memory: 919328kb

input:

187500000 5941554024261918062 17356601866920567143

output:

679191360

result:

ok single line: '679191360'

Test #9:

score: 0
Accepted
time: 383ms
memory: 919232kb

input:

1555848 157165614890794026 49792374427566422833

output:

588832126

result:

ok single line: '588832126'

Test #10:

score: 0
Accepted
time: 373ms
memory: 919228kb

input:

53814924637488000 8378901287491856069 46225409092942057365

output:

964965504

result:

ok single line: '964965504'

Test #11:

score: 0
Accepted
time: 383ms
memory: 919236kb

input:

11814720750000000 8152927138245188051 35351923956338524619

output:

183963359

result:

ok single line: '183963359'

Test #12:

score: 0
Accepted
time: 391ms
memory: 919228kb

input:

6453888000000 4334845344448208535 35982793193772682339

output:

570114022

result:

ok single line: '570114022'

Test #13:

score: 0
Accepted
time: 367ms
memory: 919516kb

input:

90071357282285400 7893548167754114409 27099084703937108974

output:

869822186

result:

ok single line: '869822186'

Test #14:

score: 0
Accepted
time: 371ms
memory: 919516kb

input:

45571065750000 177160749596350425 98884377930460959454

output:

607698665

result:

ok single line: '607698665'

Test #15:

score: 0
Accepted
time: 378ms
memory: 919328kb

input:

1128443962982400 6338876482181492537 40931938533793596007

output:

881168270

result:

ok single line: '881168270'

Test #16:

score: 0
Accepted
time: 327ms
memory: 919220kb

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 383ms
memory: 919512kb

input:

1412793457031250 2410155470167050095 99063185266833009818

output:

399813226

result:

ok single line: '399813226'

Test #18:

score: 0
Accepted
time: 376ms
memory: 919296kb

input:

67722117120000 8909573534349989418 73129289758235281558

output:

898227227

result:

ok single line: '898227227'

Test #19:

score: 0
Accepted
time: 382ms
memory: 919532kb

input:

472055808000 6809917603531307093 27494416416722163137

output:

379198478

result:

ok single line: '379198478'

Test #20:

score: 0
Accepted
time: 388ms
memory: 919304kb

input:

19353600000 8687492345912514346 24058039408337150852

output:

250715555

result:

ok single line: '250715555'

Test #21:

score: 0
Accepted
time: 376ms
memory: 919236kb

input:

47855420020225440 6150828649270625443 84863934988301168136

output:

665186711

result:

ok single line: '665186711'

Test #22:

score: 0
Accepted
time: 378ms
memory: 919516kb

input:

1382400000 9545797804645162278 70441077437727026904

output:

278230087

result:

ok single line: '278230087'

Test #23:

score: 0
Accepted
time: 357ms
memory: 919520kb

input:

816293376 2952089614708276156 10939708785225040670

output:

120954190

result:

ok single line: '120954190'

Test #24:

score: 0
Accepted
time: 386ms
memory: 919304kb

input:

4185097875 1348426133484952253 56617823359794500344

output:

773995224

result:

ok single line: '773995224'

Test #25:

score: 0
Accepted
time: 368ms
memory: 919228kb

input:

5828945117184 7777082394971366991 63470232991138132969

output:

678496908

result:

ok single line: '678496908'

Test #26:

score: 0
Accepted
time: 382ms
memory: 919224kb

input:

16184770560 3869053219872876321 94590086601168840932

output:

168181821

result:

ok single line: '168181821'

Test #27:

score: 0
Accepted
time: 345ms
memory: 919448kb

input:

2 1 12

output:

6

result:

ok single line: '6'

Test #28:

score: 0
Accepted
time: 378ms
memory: 919224kb

input:

30146484375 290228705524339176 51853415145287716863

output:

229436627

result:

ok single line: '229436627'

Test #29:

score: 0
Accepted
time: 374ms
memory: 919288kb

input:

2072513819443200 3726664558969607832 42501102605103061370

output:

947952932

result:

ok single line: '947952932'

Test #30:

score: 0
Accepted
time: 374ms
memory: 919456kb

input:

9920232000000000 4602219263214498291 80783137037024823899

output:

846877519

result:

ok single line: '846877519'

Test #31:

score: 0
Accepted
time: 372ms
memory: 919224kb

input:

97200000000000000 9310820760839688870 35322929083473756214

output:

936587432

result:

ok single line: '936587432'

Test #32:

score: 0
Accepted
time: 391ms
memory: 919232kb

input:

45209390625 5752361069878044328 64635325028527078951

output:

578047592

result:

ok single line: '578047592'

Test #33:

score: 0
Accepted
time: 383ms
memory: 919496kb

input:

54442233216000 2452030574225118723 90982734056131320662

output:

417646585

result:

ok single line: '417646585'

Test #34:

score: 0
Accepted
time: 380ms
memory: 919300kb

input:

1530550080000 7431421026778839808 84825282227911272129

output:

600103842

result:

ok single line: '600103842'

Test #35:

score: 0
Accepted
time: 364ms
memory: 919236kb

input:

13765147361280 4924477486471254843 10002324705150566233

output:

951883713

result:

ok single line: '951883713'

Test #36:

score: 0
Accepted
time: 382ms
memory: 919484kb

input:

59825698242187500 6303744363677706767 91410210495502213963

output:

774734375

result:

ok single line: '774734375'

Test #37:

score: 0
Accepted
time: 379ms
memory: 919292kb

input:

110658879959040 2133591391458550040 48494371567095341228

output:

103505650

result:

ok single line: '103505650'

Test #38:

score: 0
Accepted
time: 340ms
memory: 919220kb

input:

1 3 100

output:

98

result:

ok single line: '98'

Test #39:

score: 0
Accepted
time: 380ms
memory: 919296kb

input:

3160365465600 8968721517098518892 78444481529635953131

output:

364620926

result:

ok single line: '364620926'

Test #40:

score: 0
Accepted
time: 368ms
memory: 919512kb

input:

54838448056132899 4242999884713464056 92948071680698209741

output:

922087167

result:

ok single line: '922087167'

Test #41:

score: 0
Accepted
time: 423ms
memory: 919304kb

input:

78183771565555182 7823307199080715671 93466469990450000599

output:

635073629

result:

ok single line: '635073629'

Test #42:

score: 0
Accepted
time: 375ms
memory: 919452kb

input:

56555532446322947 2952925229100796893 35926880503684324113

output:

663547216

result:

ok single line: '663547216'

Test #43:

score: 0
Accepted
time: 357ms
memory: 919300kb

input:

15701121272683095 8633703383009071570 55273589042372583668

output:

253996413

result:

ok single line: '253996413'

Test #44:

score: 0
Accepted
time: 368ms
memory: 919296kb

input:

11914467542453704 2857068399817941722 83230805830740136213

output:

956698341

result:

ok single line: '956698341'

Test #45:

score: 0
Accepted
time: 378ms
memory: 919332kb

input:

28181999963152819 7948365158338416594 87742700746768593189

output:

720016372

result:

ok single line: '720016372'

Test #46:

score: 0
Accepted
time: 371ms
memory: 919300kb

input:

85409868208332321 3921672860136397259 55474188860042435613

output:

622329181

result:

ok single line: '622329181'

Test #47:

score: 0
Accepted
time: 380ms
memory: 919176kb

input:

14748052718175068 9293071633738211123 85443373435217434149

output:

38392129

result:

ok single line: '38392129'

Test #48:

score: 0
Accepted
time: 384ms
memory: 919336kb

input:

41002058985303228 6141335647135876923 78910335860595680506

output:

665823537

result:

ok single line: '665823537'

Test #49:

score: 0
Accepted
time: 342ms
memory: 919336kb

input:

4 3 123

output:

62

result:

ok single line: '62'

Test #50:

score: 0
Accepted
time: 368ms
memory: 919268kb

input:

100000000000000000 3 100000000000000000000

output:

302574822

result:

ok single line: '302574822'

Test #51:

score: 0
Accepted
time: 343ms
memory: 919228kb

input:

6 7 12034

output:

9505

result:

ok single line: '9505'

Test #52:

score: 0
Accepted
time: 345ms
memory: 919516kb

input:

7 8 43021

output:

25028

result:

ok single line: '25028'

Test #53:

score: 0
Accepted
time: 360ms
memory: 919272kb

input:

8 8 43021

output:

32619

result:

ok single line: '32619'

Test #54:

score: 0
Accepted
time: 344ms
memory: 919516kb

input:

9 800 43021

output:

30930

result:

ok single line: '30930'
English 繁體中文 简体中文

伺服器時間: 2024-12-03 05:02:15 | 開源專案