QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#84522#1875. NeinmagicduckAC ✓302ms3540kbC++141.9kb2023-03-06 15:35:462023-03-06 15:35:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 15:35:51]
  • 评测
  • 测评结果:AC
  • 用时:302ms
  • 内存:3540kb
  • [2023-03-06 15:35:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T> inline void read(T &FF) {
    int RR = 1; FF = 0; char CH = getchar();
    for(; !isdigit(CH); CH = getchar()) if(CH == '-') RR = -RR;
    for(; isdigit(CH); CH = getchar()) FF = FF * 10 + CH - 48;
    FF *= RR;
}
inline void file(string str) {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 42;
LL g[N][N * 9];
void Add(LL &x, LL y) {
	x += y; x = min(x, (LL)(2e18));
}
LL mul(LL x, LL y) {
	return min((__int128)(2e18), (__int128)(x) * y);
}
void init() {
	g[0][0] = 1;
	for(int i = 1; i <= 40; i++)
		for(int j = 0; j <= i * 8; j++)
			for(int k = 0; k <= 8; k++)
				if(k <= j) Add(g[i][j], g[i - 1][j - k]);
}
int k; LL n, f[N][N];
LL calc(__int128 x, int l) {
	memset(f, 0, sizeof(f)); f[0][0] = 1;
	for(int i = 1; i <= k; i++, x /= 10) {
		const int len = (i <= l % k ? (l - 1) / k + 1 : l / k);
		for(int j = 0; j <= 40; j++)
			for(int k = (x - j + 40) % 10; k <= 320; k += 10)
				Add(f[i][(j + k) / 10], mul(g[len][k], f[i - 1][j]));
	}
	x = min(x, (__int128)(40)); return f[k][x];
}
void print(__int128 x) {
	if(x < 10) {
		putchar('0' + x); return;
	}
	print(x / 10); putchar('0' + x % 10);
}
int main() {
    //file("");
	read(k), read(n); n++; init();
	LL m = 1;
	for(int i = 1; i <= k; i++) m = m * 10; m--;
	LL s = 0; __int128 ans = 0;
	for(int i = 38; i >= 1; i--) {
		LL r = 1; __int128 G = 1;
		for(int j = 1; j < i; j++) G = G * 10;
		for(int j = 1; j < i; j++) r = (__int128)(r) * 10 % m;
		for(int j = 0; j <= 8; j++) {
			LL sum = 0;
			for(int v = 0; v <= 20; v++)
				Add(sum, calc(s + v * (__int128)(m), i - 1));
			if(sum >= n) break;
			n -= sum; ans += G; s = (s + m - r) % m;
		}
	}
	//assert(ans % m == 0);
	ans /= m; print(ans); puts("");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 3404kb

input:

1 1

output:

2

result:

ok answer is '2'

Test #2:

score: 0
Accepted
time: 6ms
memory: 3460kb

input:

1 8

output:

9

result:

ok answer is '9'

Test #3:

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

input:

1 9

output:

12

result:

ok answer is '12'

Test #4:

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

input:

1 10

output:

13

result:

ok answer is '13'

Test #5:

score: 0
Accepted
time: 31ms
memory: 3384kb

input:

5 1

output:

11112

result:

ok answer is '11112'

Test #6:

score: 0
Accepted
time: 37ms
memory: 3412kb

input:

5 84

output:

11235

result:

ok answer is '11235'

Test #7:

score: 0
Accepted
time: 35ms
memory: 3472kb

input:

5 668

output:

12345

result:

ok answer is '12345'

Test #8:

score: 0
Accepted
time: 38ms
memory: 3400kb

input:

5 733942

output:

2281488

result:

ok answer is '2281488'

Test #9:

score: 0
Accepted
time: 286ms
memory: 3540kb

input:

18 528599760553218747

output:

30725517742188427234

result:

ok answer is '30725517742188427234'

Test #10:

score: 0
Accepted
time: 296ms
memory: 3480kb

input:

18 964828716126767591

output:

55758681752658348563

result:

ok answer is '55758681752658348563'

Test #11:

score: 0
Accepted
time: 293ms
memory: 3412kb

input:

18 401057671700316435

output:

22687686284122211545

result:

ok answer is '22687686284122211545'

Test #12:

score: 0
Accepted
time: 299ms
memory: 3464kb

input:

18 837286627273865280

output:

48255733668453323265

result:

ok answer is '48255733668453323265'

Test #13:

score: 0
Accepted
time: 297ms
memory: 3396kb

input:

18 273515582847414124

output:

15116382182883344554

result:

ok answer is '15116382182883344554'

Test #14:

score: 0
Accepted
time: 283ms
memory: 3460kb

input:

18 55923968082999579

output:

2876461768512185545

result:

ok answer is '2876461768512185545'

Test #15:

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

input:

8 715524960511324231

output:

12022650248772112989

result:

ok answer is '12022650248772112989'

Test #16:

score: 0
Accepted
time: 259ms
memory: 3540kb

input:

16 151753916084873076

output:

6182363727541142425

result:

ok answer is '6182363727541142425'

Test #17:

score: 0
Accepted
time: 16ms
memory: 3392kb

input:

2 587982875953389216

output:

4754915500630529532

result:

ok answer is '4754915500630529532'

Test #18:

score: 0
Accepted
time: 115ms
memory: 3396kb

input:

10 24211831526938061

output:

410770411555582497

result:

ok answer is '410770411555582497'

Test #19:

score: 0
Accepted
time: 302ms
memory: 3412kb

input:

18 460440787100486905

output:

26131416714411853682

result:

ok answer is '26131416714411853682'

Test #20:

score: 0
Accepted
time: 95ms
memory: 3460kb

input:

8 896669742674035749

output:

14750223579258782248

result:

ok answer is '14750223579258782248'

Test #21:

score: 0
Accepted
time: 168ms
memory: 3412kb

input:

12 556270735102360402

output:

13827553636696643430

result:

ok answer is '13827553636696643430'

Test #22:

score: 0
Accepted
time: 25ms
memory: 3540kb

input:

2 992499694970876542

output:

8147123087598806742

result:

ok answer is '8147123087598806742'

Test #23:

score: 0
Accepted
time: 102ms
memory: 3480kb

input:

9 191349424180689911

output:

3224103375245122149

result:

ok answer is '3224103375245122149'

Test #24:

score: 0
Accepted
time: 12ms
memory: 3384kb

input:

1 1000000000000000000

output:

7317596822929805779

result:

ok answer is '7317596822929805779'

Test #25:

score: 0
Accepted
time: 21ms
memory: 3388kb

input:

2 1000000000000000000

output:

8207298656583156714

result:

ok answer is '8207298656583156714'

Test #26:

score: 0
Accepted
time: 29ms
memory: 3456kb

input:

3 1000000000000000000

output:

10124840976332612776

result:

ok answer is '10124840976332612776'

Test #27:

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

input:

4 1000000000000000000

output:

11134918859204347753

result:

ok answer is '11134918859204347753'

Test #28:

score: 0
Accepted
time: 45ms
memory: 3392kb

input:

5 1000000000000000000

output:

12248384925950595769

result:

ok answer is '12248384925950595769'

Test #29:

score: 0
Accepted
time: 73ms
memory: 3408kb

input:

6 1000000000000000000

output:

13481441167144812720

result:

ok answer is '13481441167144812720'

Test #30:

score: 0
Accepted
time: 77ms
memory: 3516kb

input:

7 1000000000000000000

output:

14851839567286627600

result:

ok answer is '14851839567286627600'

Test #31:

score: 0
Accepted
time: 76ms
memory: 3476kb

input:

8 1000000000000000000

output:

16400312227388843586

result:

ok answer is '16400312227388843586'

Test #32:

score: 0
Accepted
time: 95ms
memory: 3412kb

input:

9 1000000000000000000

output:

18070802619848417970

result:

ok answer is '18070802619848417970'

Test #33:

score: 0
Accepted
time: 123ms
memory: 3392kb

input:

10 1000000000000000000

output:

18876263506622668979

result:

ok answer is '18876263506622668979'

Test #34:

score: 0
Accepted
time: 129ms
memory: 3428kb

input:

11 1000000000000000000

output:

22516357784746378893

result:

ok answer is '22516357784746378893'

Test #35:

score: 0
Accepted
time: 160ms
memory: 3384kb

input:

12 1000000000000000000

output:

25606071173776613626

result:

ok answer is '25606071173776613626'

Test #36:

score: 0
Accepted
time: 165ms
memory: 3428kb

input:

13 1000000000000000000

output:

30153652575287329992

result:

ok answer is '30153652575287329992'

Test #37:

score: 0
Accepted
time: 184ms
memory: 3404kb

input:

14 1000000000000000000

output:

34032144146113465692

result:

ok answer is '34032144146113465692'

Test #38:

score: 0
Accepted
time: 233ms
memory: 3520kb

input:

15 1000000000000000000

output:

38476235652741893950

result:

ok answer is '38476235652741893950'

Test #39:

score: 0
Accepted
time: 246ms
memory: 3476kb

input:

16 1000000000000000000

output:

44453843638835448269

result:

ok answer is '44453843638835448269'

Test #40:

score: 0
Accepted
time: 273ms
memory: 3396kb

input:

17 1000000000000000000

output:

51178357488582512218

result:

ok answer is '51178357488582512218'

Test #41:

score: 0
Accepted
time: 288ms
memory: 3520kb

input:

18 1000000000000000000

output:

57644143667246653868

result:

ok answer is '57644143667246653868'

Test #42:

score: 0
Accepted
time: 153ms
memory: 3432kb

input:

11 169906399332236675

output:

3542071158723189134

result:

ok answer is '3542071158723189134'

Test #43:

score: 0
Accepted
time: 118ms
memory: 3392kb

input:

10 836507396055528616

output:

15844261021999264957

result:

ok answer is '15844261021999264957'

Test #44:

score: 0
Accepted
time: 284ms
memory: 3468kb

input:

18 271736347334110166

output:

14838142784382116438

result:

ok answer is '14838142784382116438'

Test #45:

score: 0
Accepted
time: 189ms
memory: 3540kb

input:

13 705965302907659012

output:

20780554485617714682

result:

ok answer is '20780554485617714682'

Test #46:

score: 0
Accepted
time: 276ms
memory: 3540kb

input:

17 141194262776175153

output:

6535463816612312328

result:

ok answer is '6535463816612312328'

Test #47:

score: 0
Accepted
time: 139ms
memory: 3464kb

input:

12 575423218349724000

output:

14318523724188758677

result:

ok answer is '14318523724188758677'

Test #48:

score: 0
Accepted
time: 128ms
memory: 3408kb

input:

11 10652178218240141

output:

201716847375538682

result:

ok answer is '201716847375538682'

Test #49:

score: 0
Accepted
time: 226ms
memory: 3408kb

input:

15 677253166351597490

output:

25718425137845667325

result:

ok answer is '25718425137845667325'

Test #50:

score: 0
Accepted
time: 224ms
memory: 3416kb

input:

14 112482121925146336

output:

3478827471866842353

result:

ok answer is '3478827471866842353'

Test #51:

score: 0
Accepted
time: 165ms
memory: 3460kb

input:

13 138182159835368774

output:

3736504553128889177

result:

ok answer is '3736504553128889177'

Test #52:

score: 0
Accepted
time: 286ms
memory: 3436kb

input:

17 572411115408917620

output:

28263577418567266116

result:

ok answer is '28263577418567266116'

Test #53:

score: 0
Accepted
time: 241ms
memory: 3404kb

input:

16 7640070982466466

output:

275752565647555878

result:

ok answer is '275752565647555878'

Test #54:

score: 0
Accepted
time: 230ms
memory: 3476kb

input:

15 441869026556015312

output:

16212131234378684940

result:

ok answer is '16212131234378684940'

Test #55:

score: 0
Accepted
time: 192ms
memory: 3412kb

input:

14 876097982129564158

output:

30138111462733879719

result:

ok answer is '30138111462733879719'

Test #56:

score: 0
Accepted
time: 287ms
memory: 3436kb

input:

18 543698978852856099

output:

31531851816668641477

result:

ok answer is '31531851816668641477'

Test #57:

score: 0
Accepted
time: 265ms
memory: 3392kb

input:

17 977927934426404945

output:

50224732558555875933

result:

ok answer is '50224732558555875933'

Test #58:

score: 0
Accepted
time: 257ms
memory: 3476kb

input:

16 413156889999953790

output:

17247527871564162333

result:

ok answer is '17247527871564162333'

Test #59:

score: 0
Accepted
time: 219ms
memory: 3472kb

input:

15 847385845573502637

output:

32858466436756182939

result:

ok answer is '32858466436756182939'

Test #60:

score: 0
Accepted
time: 121ms
memory: 3520kb

input:

10 282614801147051482

output:

5234025743251842898

result:

ok answer is '5234025743251842898'

Test #61:

score: 0
Accepted
time: 217ms
memory: 3540kb

input:

15 973760833528793663

output:

37522313475261748199

result:

ok answer is '37522313475261748199'

Test #62:

score: 0
Accepted
time: 138ms
memory: 3520kb

input:

10 408989789102342508

output:

7507683644212199226

result:

ok answer is '7507683644212199226'

Test #63:

score: 0
Accepted
time: 292ms
memory: 3400kb

input:

18 843218748970858650

output:

48517453136216784320

result:

ok answer is '48517453136216784320'

Test #64:

score: 0
Accepted
time: 282ms
memory: 3460kb

input:

17 278447704544407496

output:

13445647446417261863

result:

ok answer is '13445647446417261863'

Test #65:

score: 0
Accepted
time: 265ms
memory: 3412kb

input:

16 712676664412923638

output:

31626684778484371838

result:

ok answer is '31626684778484371838'

Test #66:

score: 0
Accepted
time: 125ms
memory: 3408kb

input:

11 147905615691505187

output:

3115037238176298995

result:

ok answer is '3115037238176298995'

Test #67:

score: 0
Accepted
time: 201ms
memory: 3392kb

input:

14 814506608119829833

output:

27141557811571426774

result:

ok answer is '27141557811571426774'

Test #68:

score: 0
Accepted
time: 285ms
memory: 3460kb

input:

18 249735567988345974

output:

13745718855311428535

result:

ok answer is '13745718855311428535'

Test #69:

score: 0
Accepted
time: 276ms
memory: 3436kb

input:

17 683964523561894820

output:

34462588212244874220

result:

ok answer is '34462588212244874220'

Test #70:

score: 0
Accepted
time: 188ms
memory: 3408kb

input:

12 119193479135443666

output:

2777183132661531726

result:

ok answer is '2777183132661531726'

Test #71:

score: 0
Accepted
time: 289ms
memory: 3416kb

input:

18 577967474662410047

output:

33372657423746582198

result:

ok answer is '33372657423746582198'