QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#322692#7954. Special Numberssgweo8ysWA 654ms232328kbC++144.7kb2024-02-07 15:53:352024-02-07 15:53:35

Judging History

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

  • [2024-02-07 15:53:35]
  • 评测
  • 测评结果：WA
  • 用时：654ms
  • 内存：232328kb
查看
  • [2024-02-07 15:53:35]
  • 提交

answer

#include <bits/stdc++.h>
#define int __int128
using namespace std;
typedef __int128 LL;

const int p = 1000000007;

int add(int x, int y) { return x + y < p ? x + y : x + y - p; }

LL k, k2, k3, k5, k7, pw9[30];
LL f[2][2][2][65][45][25][25], v[25], n;
LL g[2][2][2][2];

int val[10][4] = {
    {0, 0, 0, 0},
    {0, 0, 0, 0},
    {1, 0, 0, 0},
    {0, 1, 0, 0},
    {2, 0, 0, 0},
    {0, 0, 1, 0},
    {1, 1, 0, 0},
    {0, 0, 0, 1},
    {3, 0, 0, 0},
    {0, 2, 0, 0},
};

long long solve(LL mx)
{
    memset(f, 0, sizeof(f));
    LL c = 0, ans = 0;
    n = 0;
    while(mx) v[++n] = mx % 10, mx /= 10;
    //cout << (n == 21) << endl;
    reverse(v + 1, v + n + 1);
    f[1][1][1][0][0][0][0] = 1;
    for(int i = 1; i <= n; i++){
        memset(f[c], 0, sizeof(f[c]));
        f[c][0][1][0][0][0][0] = 1;

        for(int i2 = 0; i2 <= 3 * n; i2++){
            for(int i3 = 0; i3 <= 2 * n; i3++){
                for(int i5 = 0; i5 <= n; i5++){
                    for(int i7 = 0; i7 <= n; i7++){
                        LL sum = f[c ^ 1][0][0][i2][i3][i5][i7] + f[c ^ 1][0][1][i2][i3][i5][i7] + f[c ^ 1][1][0][i2][i3][i5][i7] + f[c ^ 1][1][1][i2][i3][i5][i7];
                        if(sum == 0) continue;
                        for(int x = 1; x <= 9; x++){
                            int n2 = i2 + val[x][0];
                            int n3 = i3 + val[x][1];
                            int n5 = i5 + val[x][2];
                            int n7 = i7 + val[x][3];
                            f[c][0][0][n2][n3][n5][n7] = add(f[c][0][0][n2][n3][n5][n7], add(f[c ^ 1][0][0][i2][i3][i5][i7], f[c ^ 1][0][1][i2][i3][i5][i7]));
                            if(x < v[i]){
                                f[c][0][0][n2][n3][n5][n7] = add(f[c][0][0][n2][n3][n5][n7], add(f[c ^ 1][1][0][i2][i3][i5][i7], f[c ^ 1][1][1][i2][i3][i5][i7]));
                            }
                            if(x == v[i]){
                                f[c][1][0][n2][n3][n5][n7] = add(f[c][1][0][n2][n3][n5][n7], add(f[c ^ 1][1][0][i2][i3][i5][i7], f[c ^ 1][1][1][i2][i3][i5][i7]));
                            }
                        }
                    }
                }
            }
        }
        c ^= 1;
    }
    for(int i2 = k2; i2 <= 3 * n; i2++){
        for(int i3 = k3; i3 <= 2 * n; i3++){
            for(int i5 = k5; i5 <= n; i5++){
                for(int i7 = k7; i7 <= n; i7++){
                    ans += f[c ^ 1][0][0][i2][i3][i5][i7];
                    ans += f[c ^ 1][0][1][i2][i3][i5][i7];
                    ans += f[c ^ 1][1][0][i2][i3][i5][i7];
                    ans += f[c ^ 1][1][1][i2][i3][i5][i7];
                    ans %= p;
                }
            }
        }
    }

    //cout << (long long)ans << endl;

    memset(g, 0, sizeof(g));
    c = 1;
    g[0][1][1][0] = 1;
    for(int i = 1; i <= n; i++){
        memset(g[c], 0, sizeof(g[c]));
        g[c][1][0][0] = 1;
        g[c][0][0][0] += (g[c ^ 1][0][0][0] + g[c ^ 1][1][0][0]) * 9;
        g[c][0][0][1] += (g[c ^ 1][0][0][1] + g[c ^ 1][1][0][1]) * 9;
        g[c][0][0][1] += g[c ^ 1][0][0][0] + g[c ^ 1][0][0][1];
        g[c][0][0][0] %= p, g[c][0][0][1] %= p;

        g[c][0][0][0] += (g[c ^ 1][0][1][0] + g[c ^ 1][1][1][0]) * max(v[i] - 1, (__int128)0ll);
        g[c][0][0][1] += (g[c ^ 1][0][1][1] + g[c ^ 1][1][1][1]) * max(v[i] - 1, (__int128)0ll);
        if(v[i] > 0) g[c][0][0][1] += g[c ^ 1][0][1][0] + g[c ^ 1][0][1][1];
        g[c][0][0][0] %= p, g[c][0][0][1] %= p;

        if(v[i] > 0) g[c][0][1][0] += g[c ^ 1][0][1][0] + g[c ^ 1][1][1][0];
        if(v[i] > 0) g[c][0][1][1] += g[c ^ 1][0][1][1] + g[c ^ 1][1][1][1];
        if(v[i] == 0) g[c][0][1][1] += g[c ^ 1][0][1][0] + g[c ^ 1][0][1][1];
        g[c][0][1][0] %= p, g[c][0][1][1] %= p;
        c ^= 1;
    }
    ans += g[c ^ 1][0][0][1] + g[c ^ 1][0][1][1] + g[c ^ 1][1][0][1] + g[c ^ 1][1][1][1];
    ans %= p;
    //cout << (long long)ans << endl << endl;
    return ans;
}

inline LL read()
{
    LL x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

signed main()
{
    ios :: sync_with_stdio(false);
    LL l, r;
    k = read(), l = read(), r = read();
    while(k % 2 == 0) k2++, k /= 2;
    while(k % 3 == 0) k3++, k /= 3;
    while(k % 5 == 0) k5++, k /= 5;
    while(k % 7 == 0) k7++, k /= 7;
    if(k > 1) return cout << "0\n", 0;
    pw9[0] = 1;
    for(int i = 1; i <= 20; i++) pw9[i] = pw9[i - 1] * 9 % p;
    cout << (long long)(((solve(r) - solve(l - 1)) % p + p) % p) << endl;
    return 0;
}
/*
1 1 109
*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 51ms
memory: 232252kb

input:

5 1 20

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 87ms
memory: 232104kb

input:

5 50 100

output:

19

result:

ok single line: '19'

Test #3:

score: 0
Accepted
time: 72ms
memory: 232128kb

input:

15 11 19

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 105ms
memory: 232132kb

input:

1 100 100000

output:

99901

result:

ok single line: '99901'

Test #5:

score: 0
Accepted
time: 28ms
memory: 232328kb

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 94ms
memory: 232280kb

input:

10 800 43021

output:

23570

result:

ok single line: '23570'

Test #7:

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

input:

1125899906842624 1 100000000000000000000

output:

555058180

result:

ok single line: '555058180'

Test #8:

score: 0
Accepted
time: 633ms
memory: 232128kb

input:

187500000 5941554024261918062 17356601866920567143

output:

679191360

result:

ok single line: '679191360'

Test #9:

score: 0
Accepted
time: 603ms
memory: 232280kb

input:

1555848 157165614890794026 49792374427566422833

output:

588832126

result:

ok single line: '588832126'

Test #10:

score: 0
Accepted
time: 622ms
memory: 232060kb

input:

53814924637488000 8378901287491856069 46225409092942057365

output:

964965504

result:

ok single line: '964965504'

Test #11:

score: 0
Accepted
time: 645ms
memory: 232084kb

input:

11814720750000000 8152927138245188051 35351923956338524619

output:

183963359

result:

ok single line: '183963359'

Test #12:

score: 0
Accepted
time: 635ms
memory: 232112kb

input:

6453888000000 4334845344448208535 35982793193772682339

output:

570114022

result:

ok single line: '570114022'

Test #13:

score: 0
Accepted
time: 636ms
memory: 232060kb

input:

90071357282285400 7893548167754114409 27099084703937108974

output:

869822186

result:

ok single line: '869822186'

Test #14:

score: 0
Accepted
time: 597ms
memory: 232040kb

input:

45571065750000 177160749596350425 98884377930460959454

output:

607698665

result:

ok single line: '607698665'

Test #15:

score: 0
Accepted
time: 654ms
memory: 232048kb

input:

1128443962982400 6338876482181492537 40931938533793596007

output:

881168270

result:

ok single line: '881168270'

Test #16:

score: 0
Accepted
time: 43ms
memory: 232320kb

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 625ms
memory: 232096kb

input:

1412793457031250 2410155470167050095 99063185266833009818

output:

399813226

result:

ok single line: '399813226'

Test #18:

score: 0
Accepted
time: 643ms
memory: 232116kb

input:

67722117120000 8909573534349989418 73129289758235281558

output:

898227227

result:

ok single line: '898227227'

Test #19:

score: 0
Accepted
time: 634ms
memory: 232068kb

input:

472055808000 6809917603531307093 27494416416722163137

output:

379198478

result:

ok single line: '379198478'

Test #20:

score: 0
Accepted
time: 650ms
memory: 232108kb

input:

19353600000 8687492345912514346 24058039408337150852

output:

250715555

result:

ok single line: '250715555'

Test #21:

score: 0
Accepted
time: 649ms
memory: 232260kb

input:

47855420020225440 6150828649270625443 84863934988301168136

output:

665186711

result:

ok single line: '665186711'

Test #22:

score: 0
Accepted
time: 645ms
memory: 232100kb

input:

1382400000 9545797804645162278 70441077437727026904

output:

278230087

result:

ok single line: '278230087'

Test #23:

score: 0
Accepted
time: 641ms
memory: 232100kb

input:

816293376 2952089614708276156 10939708785225040670

output:

120954190

result:

ok single line: '120954190'

Test #24:

score: 0
Accepted
time: 644ms
memory: 232108kb

input:

4185097875 1348426133484952253 56617823359794500344

output:

773995224

result:

ok single line: '773995224'

Test #25:

score: 0
Accepted
time: 637ms
memory: 232064kb

input:

5828945117184 7777082394971366991 63470232991138132969

output:

678496908

result:

ok single line: '678496908'

Test #26:

score: 0
Accepted
time: 635ms
memory: 232280kb

input:

16184770560 3869053219872876321 94590086601168840932

output:

168181821

result:

ok single line: '168181821'

Test #27:

score: 0
Accepted
time: 48ms
memory: 232088kb

input:

2 1 12

output:

6

result:

ok single line: '6'

Test #28:

score: 0
Accepted
time: 596ms
memory: 232104kb

input:

30146484375 290228705524339176 51853415145287716863

output:

229436627

result:

ok single line: '229436627'

Test #29:

score: 0
Accepted
time: 624ms
memory: 232312kb

input:

2072513819443200 3726664558969607832 42501102605103061370

output:

947952932

result:

ok single line: '947952932'

Test #30:

score: 0
Accepted
time: 633ms
memory: 232104kb

input:

9920232000000000 4602219263214498291 80783137037024823899

output:

846877519

result:

ok single line: '846877519'

Test #31:

score: 0
Accepted
time: 632ms
memory: 232128kb

input:

97200000000000000 9310820760839688870 35322929083473756214

output:

936587432

result:

ok single line: '936587432'

Test #32:

score: 0
Accepted
time: 640ms
memory: 232144kb

input:

45209390625 5752361069878044328 64635325028527078951

output:

578047592

result:

ok single line: '578047592'

Test #33:

score: 0
Accepted
time: 636ms
memory: 232088kb

input:

54442233216000 2452030574225118723 90982734056131320662

output:

417646585

result:

ok single line: '417646585'

Test #34:

score: 0
Accepted
time: 611ms
memory: 232324kb

input:

1530550080000 7431421026778839808 84825282227911272129

output:

600103842

result:

ok single line: '600103842'

Test #35:

score: 0
Accepted
time: 627ms
memory: 232028kb

input:

13765147361280 4924477486471254843 10002324705150566233

output:

951883713

result:

ok single line: '951883713'

Test #36:

score: 0
Accepted
time: 627ms
memory: 232124kb

input:

59825698242187500 6303744363677706767 91410210495502213963

output:

774734375

result:

ok single line: '774734375'

Test #37:

score: 0
Accepted
time: 624ms
memory: 232108kb

input:

110658879959040 2133591391458550040 48494371567095341228

output:

103505650

result:

ok single line: '103505650'

Test #38:

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

input:

1 3 100

output:

98

result:

ok single line: '98'

Test #39:

score: 0
Accepted
time: 636ms
memory: 232264kb

input:

3160365465600 8968721517098518892 78444481529635953131

output:

364620926

result:

ok single line: '364620926'

Test #40:

score: -100
Wrong Answer
time: 0ms
memory: 3620kb

input:

54838448056132899 4242999884713464056 92948071680698209741

output:

0

result:

wrong answer 1st lines differ - expected: '922087167', found: '0'
English 繁體中文 简体中文

Server Time: 2024-12-03 23:26:35 | OpenSource Project