QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#39526#1875. NeinWXYZAC ✓3ms3888kbC++231.9kb2022-07-11 00:27:002022-07-11 00:27:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-11 00:27:01]
  • 评测
  • 测评结果：AC
  • 用时：3ms
  • 内存：3888kb
查看
  • [2022-07-11 00:27:00]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using gl = __int128;

int B;
int K;
ll n, m;

gl ds[25][222];
gl p10[25];

gl f[25][25];

gl calc(int p, ll s)
{
    ll r = (m - s) % m;
    gl res = 0;
    for (int i = 0; i < B; i++)
    {
        gl v = i * m + r;
        for (int j = 0; j < 25; j++)
            for (int k = 0; k < 25; k++)
                f[j][k] = 0;
        f[0][0] = 1;
        for (int j = 0; j < K; j++)
        {
            int c = p / K + (p % K > j);
            int d = v / p10[j] % 10;
            for (int k = 0; k < B; k++)
                if (f[j][k])
                {
                    for (int l = 0; l < B; l++)
                    {
                        int z = l * 10 + d - k;
                        if (0 <= z && z <= 8 * c)
                            f[j + 1][l] += f[j][k] * ds[c][z];
                    }     
                }
        }
        res += f[K][v / p10[K]];
    }
    return res;
}

int main()
{
    scanf("%d%lld", &K, &n);
    B = (20 / K) + 2;
    n++;
    p10[0] = 1;
    for (int i = 1; i <= 20; i++)
        p10[i] = p10[i - 1] * 10;
    m = p10[K] - 1;
    ds[0][0] = 1;
    for (int i = 1; i <= B; i++)
        for (int j = 0; j <= i * 8; j++)
        {
            for (int k = 0; k <= 8 && k <= j; k++)
                ds[i][j] += ds[i - 1][j - k];
        }
    bool l0 = 1;
    gl ans = 0;
    ll s = 0;
    for (int i = B * K; i >= 0; i--)
    {
        for (int j = 0; j <= 8; j++)
        {
            gl res = calc(i, s);
            if (res >= n)
            {
                ans = ans * 10 + j;
                break;
            }
            n -= res;
            s = (s + p10[i % K]) % m;
        }
        if (ans >= m) l0 = 0;
        if (!l0)
        {
            printf("%d", int(ans / m));
            ans %= m;
        }
    }
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3840kb

input:

1 1

output:

2

result:

ok answer is '2'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3852kb

input:

1 8

output:

9

result:

ok answer is '9'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

1 9

output:

12

result:

ok answer is '12'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

1 10

output:

13

result:

ok answer is '13'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3716kb

input:

5 1

output:

11112

result:

ok answer is '11112'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3780kb

input:

5 84

output:

11235

result:

ok answer is '11235'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3812kb

input:

5 668

output:

12345

result:

ok answer is '12345'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3788kb

input:

5 733942

output:

2281488

result:

ok answer is '2281488'

Test #9:

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

input:

18 528599760553218747

output:

30725517742188427234

result:

ok answer is '30725517742188427234'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

18 964828716126767591

output:

55758681752658348563

result:

ok answer is '55758681752658348563'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3860kb

input:

18 401057671700316435

output:

22687686284122211545

result:

ok answer is '22687686284122211545'

Test #12:

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

input:

18 837286627273865280

output:

48255733668453323265

result:

ok answer is '48255733668453323265'

Test #13:

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

input:

18 273515582847414124

output:

15116382182883344554

result:

ok answer is '15116382182883344554'

Test #14:

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

input:

18 55923968082999579

output:

2876461768512185545

result:

ok answer is '2876461768512185545'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3776kb

input:

8 715524960511324231

output:

12022650248772112989

result:

ok answer is '12022650248772112989'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3660kb

input:

16 151753916084873076

output:

6182363727541142425

result:

ok answer is '6182363727541142425'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3696kb

input:

2 587982875953389216

output:

4754915500630529532

result:

ok answer is '4754915500630529532'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3776kb

input:

10 24211831526938061

output:

410770411555582497

result:

ok answer is '410770411555582497'

Test #19:

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

input:

18 460440787100486905

output:

26131416714411853682

result:

ok answer is '26131416714411853682'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3712kb

input:

8 896669742674035749

output:

14750223579258782248

result:

ok answer is '14750223579258782248'

Test #21:

score: 0
Accepted
time: 2ms
memory: 3856kb

input:

12 556270735102360402

output:

13827553636696643430

result:

ok answer is '13827553636696643430'

Test #22:

score: 0
Accepted
time: 2ms
memory: 3888kb

input:

2 992499694970876542

output:

8147123087598806742

result:

ok answer is '8147123087598806742'

Test #23:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

9 191349424180689911

output:

3224103375245122149

result:

ok answer is '3224103375245122149'

Test #24:

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

input:

1 1000000000000000000

output:

7317596822929805779

result:

ok answer is '7317596822929805779'

Test #25:

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

input:

2 1000000000000000000

output:

8207298656583156714

result:

ok answer is '8207298656583156714'

Test #26:

score: 0
Accepted
time: 2ms
memory: 3680kb

input:

3 1000000000000000000

output:

10124840976332612776

result:

ok answer is '10124840976332612776'

Test #27:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

4 1000000000000000000

output:

11134918859204347753

result:

ok answer is '11134918859204347753'

Test #28:

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

input:

5 1000000000000000000

output:

12248384925950595769

result:

ok answer is '12248384925950595769'

Test #29:

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

input:

6 1000000000000000000

output:

13481441167144812720

result:

ok answer is '13481441167144812720'

Test #30:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

7 1000000000000000000

output:

14851839567286627600

result:

ok answer is '14851839567286627600'

Test #31:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

8 1000000000000000000

output:

16400312227388843586

result:

ok answer is '16400312227388843586'

Test #32:

score: 0
Accepted
time: 2ms
memory: 3668kb

input:

9 1000000000000000000

output:

18070802619848417970

result:

ok answer is '18070802619848417970'

Test #33:

score: 0
Accepted
time: 2ms
memory: 3708kb

input:

10 1000000000000000000

output:

18876263506622668979

result:

ok answer is '18876263506622668979'

Test #34:

score: 0
Accepted
time: 2ms
memory: 3668kb

input:

11 1000000000000000000

output:

22516357784746378893

result:

ok answer is '22516357784746378893'

Test #35:

score: 0
Accepted
time: 1ms
memory: 3856kb

input:

12 1000000000000000000

output:

25606071173776613626

result:

ok answer is '25606071173776613626'

Test #36:

score: 0
Accepted
time: 2ms
memory: 3660kb

input:

13 1000000000000000000

output:

30153652575287329992

result:

ok answer is '30153652575287329992'

Test #37:

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

input:

14 1000000000000000000

output:

34032144146113465692

result:

ok answer is '34032144146113465692'

Test #38:

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

input:

15 1000000000000000000

output:

38476235652741893950

result:

ok answer is '38476235652741893950'

Test #39:

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

input:

16 1000000000000000000

output:

44453843638835448269

result:

ok answer is '44453843638835448269'

Test #40:

score: 0
Accepted
time: 2ms
memory: 3856kb

input:

17 1000000000000000000

output:

51178357488582512218

result:

ok answer is '51178357488582512218'

Test #41:

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

input:

18 1000000000000000000

output:

57644143667246653868

result:

ok answer is '57644143667246653868'

Test #42:

score: 0
Accepted
time: 2ms
memory: 3704kb

input:

11 169906399332236675

output:

3542071158723189134

result:

ok answer is '3542071158723189134'

Test #43:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

10 836507396055528616

output:

15844261021999264957

result:

ok answer is '15844261021999264957'

Test #44:

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

input:

18 271736347334110166

output:

14838142784382116438

result:

ok answer is '14838142784382116438'

Test #45:

score: 0
Accepted
time: 2ms
memory: 3688kb

input:

13 705965302907659012

output:

20780554485617714682

result:

ok answer is '20780554485617714682'

Test #46:

score: 0
Accepted
time: 2ms
memory: 3704kb

input:

17 141194262776175153

output:

6535463816612312328

result:

ok answer is '6535463816612312328'

Test #47:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

12 575423218349724000

output:

14318523724188758677

result:

ok answer is '14318523724188758677'

Test #48:

score: 0
Accepted
time: 2ms
memory: 3804kb

input:

11 10652178218240141

output:

201716847375538682

result:

ok answer is '201716847375538682'

Test #49:

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

input:

15 677253166351597490

output:

25718425137845667325

result:

ok answer is '25718425137845667325'

Test #50:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

14 112482121925146336

output:

3478827471866842353

result:

ok answer is '3478827471866842353'

Test #51:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

13 138182159835368774

output:

3736504553128889177

result:

ok answer is '3736504553128889177'

Test #52:

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

input:

17 572411115408917620

output:

28263577418567266116

result:

ok answer is '28263577418567266116'

Test #53:

score: 0
Accepted
time: 2ms
memory: 3804kb

input:

16 7640070982466466

output:

275752565647555878

result:

ok answer is '275752565647555878'

Test #54:

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

input:

15 441869026556015312

output:

16212131234378684940

result:

ok answer is '16212131234378684940'

Test #55:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

14 876097982129564158

output:

30138111462733879719

result:

ok answer is '30138111462733879719'

Test #56:

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

input:

18 543698978852856099

output:

31531851816668641477

result:

ok answer is '31531851816668641477'

Test #57:

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

input:

17 977927934426404945

output:

50224732558555875933

result:

ok answer is '50224732558555875933'

Test #58:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

16 413156889999953790

output:

17247527871564162333

result:

ok answer is '17247527871564162333'

Test #59:

score: 0
Accepted
time: 2ms
memory: 3780kb

input:

15 847385845573502637

output:

32858466436756182939

result:

ok answer is '32858466436756182939'

Test #60:

score: 0
Accepted
time: 2ms
memory: 3792kb

input:

10 282614801147051482

output:

5234025743251842898

result:

ok answer is '5234025743251842898'

Test #61:

score: 0
Accepted
time: 2ms
memory: 3764kb

input:

15 973760833528793663

output:

37522313475261748199

result:

ok answer is '37522313475261748199'

Test #62:

score: 0
Accepted
time: 2ms
memory: 3772kb

input:

10 408989789102342508

output:

7507683644212199226

result:

ok answer is '7507683644212199226'

Test #63:

score: 0
Accepted
time: 1ms
memory: 3704kb

input:

18 843218748970858650

output:

48517453136216784320

result:

ok answer is '48517453136216784320'

Test #64:

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

input:

17 278447704544407496

output:

13445647446417261863

result:

ok answer is '13445647446417261863'

Test #65:

score: 0
Accepted
time: 2ms
memory: 3776kb

input:

16 712676664412923638

output:

31626684778484371838

result:

ok answer is '31626684778484371838'

Test #66:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

11 147905615691505187

output:

3115037238176298995

result:

ok answer is '3115037238176298995'

Test #67:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

14 814506608119829833

output:

27141557811571426774

result:

ok answer is '27141557811571426774'

Test #68:

score: 0
Accepted
time: 2ms
memory: 3800kb

input:

18 249735567988345974

output:

13745718855311428535

result:

ok answer is '13745718855311428535'

Test #69:

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

input:

17 683964523561894820

output:

34462588212244874220

result:

ok answer is '34462588212244874220'

Test #70:

score: 0
Accepted
time: 2ms
memory: 3668kb

input:

12 119193479135443666

output:

2777183132661531726

result:

ok answer is '2777183132661531726'

Test #71:

score: 0
Accepted
time: 2ms
memory: 3860kb

input:

18 577967474662410047

output:

33372657423746582198

result:

ok answer is '33372657423746582198'
English 繁體中文 简体中文

服务器时间: 2025-01-20 20:01:18 | 开源项目