QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51474#1875. NeintricyzhkxAC ✓6ms3960kbC++141.0kb2022-10-02 14:56:572022-10-02 14:57:00

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-02 14:57:00]
  • 评测
  • 测评结果:AC
  • 用时:6ms
  • 内存:3960kb
  • [2022-10-02 14:56:57]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
typedef __int128 lll;
ll pw10[40];
lll f[40][40],g[40][400];
void write(lll x)
{
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
int main()
{
	g[0][0]=1;
	for(int i=1;i<40;i++)
		for(int j=0;j<=8*i;j++)
			for(int k=0;k<=8 && k<=j;k++)
				g[i][j]+=g[i-1][j-k];
	int k;
	ll n,m=1,r=0;
	cin>>k>>n;n++;
	for(int i=0;i<k;i++) m*=10;m--;
	pw10[0]=1;
	for(int i=1;i<40;i++) pw10[i]=pw10[i-1]*10%m;
	lll ans=0;
	for(int i=39;i>=0;i--)
	{
		int x=0,b=(i+k-1)/k;
		for(;x<9;x++,r=(r+pw10[i])%m)
		{
			lll s=(m-r)%m,cnt=0;
			for(;s<=(lll)b*(m-1);s+=m)
			{
				memset(f,0,sizeof(f));
				f[0][0]=1;
				lll ts=s;
				for(int p=0;p<k;p++,ts/=10)
					for(int q=0;q<b;q++)
						for(int tq=0;tq<b;tq++)
						{
							int t=10*tq-q+ts%10;
							if(t>=0 && t<400) f[p+1][tq]+=f[p][q]*g[(i-p+k-1)/k][t];
						}
				cnt+=f[k][ts];
			}
			if(cnt>=n) break;
			else n-=cnt;
		}
		ans=ans*10+x;
	}
	write(ans/m);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3944kb

input:

1 1

output:

2

result:

ok answer is '2'

Test #2:

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

input:

1 8

output:

9

result:

ok answer is '9'

Test #3:

score: 0
Accepted
time: 5ms
memory: 3944kb

input:

1 9

output:

12

result:

ok answer is '12'

Test #4:

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

input:

1 10

output:

13

result:

ok answer is '13'

Test #5:

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

input:

5 1

output:

11112

result:

ok answer is '11112'

Test #6:

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

input:

5 84

output:

11235

result:

ok answer is '11235'

Test #7:

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

input:

5 668

output:

12345

result:

ok answer is '12345'

Test #8:

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

input:

5 733942

output:

2281488

result:

ok answer is '2281488'

Test #9:

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

input:

18 528599760553218747

output:

30725517742188427234

result:

ok answer is '30725517742188427234'

Test #10:

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

input:

18 964828716126767591

output:

55758681752658348563

result:

ok answer is '55758681752658348563'

Test #11:

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

input:

18 401057671700316435

output:

22687686284122211545

result:

ok answer is '22687686284122211545'

Test #12:

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

input:

18 837286627273865280

output:

48255733668453323265

result:

ok answer is '48255733668453323265'

Test #13:

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

input:

18 273515582847414124

output:

15116382182883344554

result:

ok answer is '15116382182883344554'

Test #14:

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

input:

18 55923968082999579

output:

2876461768512185545

result:

ok answer is '2876461768512185545'

Test #15:

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

input:

8 715524960511324231

output:

12022650248772112989

result:

ok answer is '12022650248772112989'

Test #16:

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

input:

16 151753916084873076

output:

6182363727541142425

result:

ok answer is '6182363727541142425'

Test #17:

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

input:

2 587982875953389216

output:

4754915500630529532

result:

ok answer is '4754915500630529532'

Test #18:

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

input:

10 24211831526938061

output:

410770411555582497

result:

ok answer is '410770411555582497'

Test #19:

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

input:

18 460440787100486905

output:

26131416714411853682

result:

ok answer is '26131416714411853682'

Test #20:

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

input:

8 896669742674035749

output:

14750223579258782248

result:

ok answer is '14750223579258782248'

Test #21:

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

input:

12 556270735102360402

output:

13827553636696643430

result:

ok answer is '13827553636696643430'

Test #22:

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

input:

2 992499694970876542

output:

8147123087598806742

result:

ok answer is '8147123087598806742'

Test #23:

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

input:

9 191349424180689911

output:

3224103375245122149

result:

ok answer is '3224103375245122149'

Test #24:

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

input:

1 1000000000000000000

output:

7317596822929805779

result:

ok answer is '7317596822929805779'

Test #25:

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

input:

2 1000000000000000000

output:

8207298656583156714

result:

ok answer is '8207298656583156714'

Test #26:

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

input:

3 1000000000000000000

output:

10124840976332612776

result:

ok answer is '10124840976332612776'

Test #27:

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

input:

4 1000000000000000000

output:

11134918859204347753

result:

ok answer is '11134918859204347753'

Test #28:

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

input:

5 1000000000000000000

output:

12248384925950595769

result:

ok answer is '12248384925950595769'

Test #29:

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

input:

6 1000000000000000000

output:

13481441167144812720

result:

ok answer is '13481441167144812720'

Test #30:

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

input:

7 1000000000000000000

output:

14851839567286627600

result:

ok answer is '14851839567286627600'

Test #31:

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

input:

8 1000000000000000000

output:

16400312227388843586

result:

ok answer is '16400312227388843586'

Test #32:

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

input:

9 1000000000000000000

output:

18070802619848417970

result:

ok answer is '18070802619848417970'

Test #33:

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

input:

10 1000000000000000000

output:

18876263506622668979

result:

ok answer is '18876263506622668979'

Test #34:

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

input:

11 1000000000000000000

output:

22516357784746378893

result:

ok answer is '22516357784746378893'

Test #35:

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

input:

12 1000000000000000000

output:

25606071173776613626

result:

ok answer is '25606071173776613626'

Test #36:

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

input:

13 1000000000000000000

output:

30153652575287329992

result:

ok answer is '30153652575287329992'

Test #37:

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

input:

14 1000000000000000000

output:

34032144146113465692

result:

ok answer is '34032144146113465692'

Test #38:

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

input:

15 1000000000000000000

output:

38476235652741893950

result:

ok answer is '38476235652741893950'

Test #39:

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

input:

16 1000000000000000000

output:

44453843638835448269

result:

ok answer is '44453843638835448269'

Test #40:

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

input:

17 1000000000000000000

output:

51178357488582512218

result:

ok answer is '51178357488582512218'

Test #41:

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

input:

18 1000000000000000000

output:

57644143667246653868

result:

ok answer is '57644143667246653868'

Test #42:

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

input:

11 169906399332236675

output:

3542071158723189134

result:

ok answer is '3542071158723189134'

Test #43:

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

input:

10 836507396055528616

output:

15844261021999264957

result:

ok answer is '15844261021999264957'

Test #44:

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

input:

18 271736347334110166

output:

14838142784382116438

result:

ok answer is '14838142784382116438'

Test #45:

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

input:

13 705965302907659012

output:

20780554485617714682

result:

ok answer is '20780554485617714682'

Test #46:

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

input:

17 141194262776175153

output:

6535463816612312328

result:

ok answer is '6535463816612312328'

Test #47:

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

input:

12 575423218349724000

output:

14318523724188758677

result:

ok answer is '14318523724188758677'

Test #48:

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

input:

11 10652178218240141

output:

201716847375538682

result:

ok answer is '201716847375538682'

Test #49:

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

input:

15 677253166351597490

output:

25718425137845667325

result:

ok answer is '25718425137845667325'

Test #50:

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

input:

14 112482121925146336

output:

3478827471866842353

result:

ok answer is '3478827471866842353'

Test #51:

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

input:

13 138182159835368774

output:

3736504553128889177

result:

ok answer is '3736504553128889177'

Test #52:

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

input:

17 572411115408917620

output:

28263577418567266116

result:

ok answer is '28263577418567266116'

Test #53:

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

input:

16 7640070982466466

output:

275752565647555878

result:

ok answer is '275752565647555878'

Test #54:

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

input:

15 441869026556015312

output:

16212131234378684940

result:

ok answer is '16212131234378684940'

Test #55:

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

input:

14 876097982129564158

output:

30138111462733879719

result:

ok answer is '30138111462733879719'

Test #56:

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

input:

18 543698978852856099

output:

31531851816668641477

result:

ok answer is '31531851816668641477'

Test #57:

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

input:

17 977927934426404945

output:

50224732558555875933

result:

ok answer is '50224732558555875933'

Test #58:

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

input:

16 413156889999953790

output:

17247527871564162333

result:

ok answer is '17247527871564162333'

Test #59:

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

input:

15 847385845573502637

output:

32858466436756182939

result:

ok answer is '32858466436756182939'

Test #60:

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

input:

10 282614801147051482

output:

5234025743251842898

result:

ok answer is '5234025743251842898'

Test #61:

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

input:

15 973760833528793663

output:

37522313475261748199

result:

ok answer is '37522313475261748199'

Test #62:

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

input:

10 408989789102342508

output:

7507683644212199226

result:

ok answer is '7507683644212199226'

Test #63:

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

input:

18 843218748970858650

output:

48517453136216784320

result:

ok answer is '48517453136216784320'

Test #64:

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

input:

17 278447704544407496

output:

13445647446417261863

result:

ok answer is '13445647446417261863'

Test #65:

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

input:

16 712676664412923638

output:

31626684778484371838

result:

ok answer is '31626684778484371838'

Test #66:

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

input:

11 147905615691505187

output:

3115037238176298995

result:

ok answer is '3115037238176298995'

Test #67:

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

input:

14 814506608119829833

output:

27141557811571426774

result:

ok answer is '27141557811571426774'

Test #68:

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

input:

18 249735567988345974

output:

13745718855311428535

result:

ok answer is '13745718855311428535'

Test #69:

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

input:

17 683964523561894820

output:

34462588212244874220

result:

ok answer is '34462588212244874220'

Test #70:

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

input:

12 119193479135443666

output:

2777183132661531726

result:

ok answer is '2777183132661531726'

Test #71:

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

input:

18 577967474662410047

output:

33372657423746582198

result:

ok answer is '33372657423746582198'