QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#751029	#6199. 数圈圈	jinqihao2023	20	10ms	37692kb	C++14	981b	2024-11-15 16:48:32	2024-11-15 16:48:33

Judging History

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

[2024-11-15 16:48:33]
评测

测评结果：20
用时：10ms
内存：37692kb

查看

[2024-11-15 16:48:32]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,mod=998244353;
int tid,n,x,f[N][N],a[N],ans[N];
int main()
{
	//freopen("story5.in","r",stdin);
	//freopen("story.out","w",stdout);
	scanf("%d %d",&n,&x);
	bool fl1=1;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<n;i++)fl1&=(a[i]<=a[i+1]);
	if(fl1)
	{
		f[0][0]=1;
		for(int i=1;i<=n;i++)for(int j=0;j<=i;j++)
		{
			f[i][j]=f[i-1][j];
			if(j>0)
			{
				if(a[i]>=i)f[i][j]=(f[i][j]+1ll*f[i-1][j-1]*(a[i]-j+x))%mod;
				else f[i][j]=(f[i][j]+1ll*f[i-1][j-1]*max(0,a[i]-j+1))%mod;
			}
		}
		for(int i=0;i<=n;i++)printf("%d ",f[n][i]);printf("\n");
		return 0;
	}
	f[n+1][0]=1;
	for(int i=n;i>=1;i--)for(int j=0;j<=n-i+1;j++)
	{
		f[i][j]=f[i+1][j];
		if(j>0)
		{
			if(a[i]>=i)f[i][j]=(f[i][j]+1ll*f[i+1][j-1]*(a[i]-j+x))%mod;
			else f[i][j]=(f[i][j]+1ll*f[i+1][j-1]*max(0,a[i]-j+1))%mod;
		}
	}
	for(int i=0;i<=n;i++)printf("%d ",f[1][i]);printf("\n");
	return 0;
}

源文件, 语言: C++14

详细

Subtask #1:

score: 1

Accepted

Test #1:

score: 1

Accepted

time: 0ms

memory: 3964kb

input:

1 915080344
1

output:

1 915080344

result:

ok 2 number(s): "1 915080344"

Test #2:

score: 1

Accepted

time: 0ms

memory: 3868kb

input:

1 915080344
0

output:

1 0

result:

ok 2 number(s): "1 0"

Test #3:

score: 1

Accepted

time: 0ms

memory: 3944kb

input:

8 60641044
8 8 8 8 8 8 8 8

output:

1 485128408 47996075 379627744 150492470 955348304 893852780 400745432 184663991

result:

ok 9 numbers

Test #4:

score: 1

Accepted

time: 0ms

memory: 3936kb

input:

8 5015523
0 0 0 0 0 0 0 1

output:

1 1 0 0 0 0 0 0 0

result:

ok 9 numbers

Test #5:

score: 1

Accepted

time: 0ms

memory: 3928kb

input:

6 469476507
0 0 3 4 4 4

output:

1 938953027 685386746 814057889 85780770 0 0

result:

ok 7 numbers

Test #6:

score: 1

Accepted

time: 0ms

memory: 3948kb

input:

8 430768932
0 2 2 3 4 6 6 7

output:

1 861537892 8385549 91551398 546166364 364018503 783811192 746026358 0

result:

ok 9 numbers

Test #7:

score: 1

Accepted

time: 0ms

memory: 3872kb

input:

7 861726531
0 0 6 6 6 6 6

output:

1 452173091 675192946 823218157 246524395 422107531 0 0

result:

ok 8 numbers

Subtask #2:

score: 9

Accepted

Test #8:

score: 9

Accepted

time: 0ms

memory: 4020kb

input:

15 0
1 1 1 3 6 8 10 11 11 12 13 13 14 15 15

output:

1 122 6222 173976 2941896 31329936 212468976 908747712 384836990 634979325 959428094 118389247 151372800 4147200 0 0

result:

ok 16 numbers

Test #9:

score: 9

Accepted

time: 0ms

memory: 4016kb

input:

15 0
0 0 0 0 0 0 0 0 0 0 13 14 14 14 14

output:

1 65 1563 17268 86988 158400 0 0 0 0 0 0 0 0 0 0

result:

ok 16 numbers

Test #10:

score: 9

Accepted

time: 0ms

memory: 3860kb

input:

15 0
3 7 7 7 7 7 7 7 7 10 10 10 10 10 10

output:

1 111 5069 124376 1797880 15805440 84299040 264216960 454083840 373161600 105840000 0 0 0 0 0

result:

ok 16 numbers

Test #11:

score: 9

Accepted

time: 0ms

memory: 3848kb

input:

15 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 10

output:

1 11 9 0 0 0 0 0 0 0 0 0 0 0 0 0

result:

ok 16 numbers

Test #12:

score: 9

Accepted

time: 0ms

memory: 3840kb

input:

15 0
0 0 2 5 5 5 7 7 11 11 13 15 15 15 15

output:

1 116 5599 147353 2329717 23009526 143249418 555150240 297223999 718560223 175587487 352356480 34439040 552960 0 0

result:

ok 16 numbers

Test #13:

score: 9

Accepted

time: 0ms

memory: 3964kb

input:

1 0
1

output:

1 0

result:

ok 2 number(s): "1 0"

Subtask #3:

score: 10

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #14:

score: 10

Accepted

time: 10ms

memory: 36752kb

input:

1999 534253321
3 4 6 7 7 8 8 8 9 11 12 14 14 15 16 17 18 18 19 19 19 20 22 22 26 27 28 30 31 32 34 34 35 35 35 36 37 37 38 40 42 43 44 45 47 48 50 51 52 52 52 53 54 55 55 55 57 57 58 59 61 62 64 65 65 66 66 69 69 69 69 69 71 72 72 73 73 74 76 77 79 79 81 81 82 84 85 86 86 88 92 94 95 97 97 98 99 99 ...

output:

1 953211139 257568325 220501105 623433961 180031559 833037467 396983849 209899998 53230560 141504779 968307116 372883144 837211358 802540431 812215686 328261448 263381741 600310675 795356284 742542522 498781038 872853450 580687976 717285974 83199455 314428424 264355776 63288458 576374064 529079484 5...

result:

ok 2000 numbers

Test #15:

score: 10

Accepted

time: 3ms

memory: 37692kb

input:

1999 796334686
0 0 2 4 4 7 7 9 9 9 12 12 12 12 12 12 14 14 16 16 19 23 23 23 23 26 28 28 29 30 30 31 37 37 37 37 37 39 39 39 39 39 39 39 39 41 43 45 46 46 48 48 51 51 54 54 54 55 56 59 59 59 59 59 59 59 61 61 61 61 61 62 66 66 69 69 69 71 71 71 72 72 72 74 81 81 84 89 89 94 95 97 99 101 101 101 102 ...

output:

1 536002349 937757160 289425713 907882641 321783010 595662029 556853988 786788251 529488064 794023762 421672954 686250945 968035887 784085910 575322365 429895268 902593974 1846999 293576649 428461188 235553244 257045333 570459588 747748543 856031574 169520023 560332363 980410837 392913972 367618628 ...

result:

ok 2000 numbers

Test #16:

score: 10

Accepted

time: 5ms

memory: 28740kb

input:

1999 305107443
0 0 0 0 0 0 0 0 0 0 3 3 3 9 11 11 14 14 14 17 24 24 24 24 26 26 26 26 29 29 29 34 34 37 37 37 39 42 42 42 42 42 42 42 42 47 48 48 48 50 50 54 54 54 57 57 57 63 63 63 72 72 72 72 72 81 81 81 81 81 81 81 87 92 92 95 99 99 99 102 108 108 108 108 108 108 108 108 108 109 109 109 109 109 10...

output:

1 969126377 537226299 728367360 209560166 989924837 253940627 427351981 914061019 628496118 734719309 252926245 583312948 68786973 258073259 910788167 299137224 885656052 875969853 354404451 45716584 320441751 277290512 954948659 211035762 146845140 494632707 610355600 899795592 163072490 635966446 ...

result:

ok 2000 numbers

Test #17:

score: 10

Accepted

time: 7ms

memory: 19756kb

input:

1998 709560295
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

1 5774 12268627 333251810 968490666 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 1999 numbers

Test #18:

score: 10

Accepted

time: 0ms

memory: 19712kb

input:

1998 692932808
1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 1995 ...

output:

1 917063734 948290819 579651779 337834497 220466570 90399482 618308924 735098912 260820378 131547200 700587221 174762056 363003551 158023649 403987675 152162315 356539929 214887886 516517666 514687892 843687841 780208121 404306050 676949444 844822526 575059869 466021734 937954972 852880314 430298147...

result:

ok 1999 numbers

Subtask #4:

score: 0

Runtime Error

Test #19:

score: 0

Runtime Error

input:

74999 1
1 2 3 3 4 4 4 4 4 4 4 4 7 8 8 9 9 9 10 13 13 14 14 16 19 20 21 22 24 25 25 26 26 29 31 32 32 35 35 36 38 39 39 40 41 43 43 44 45 45 45 46 48 49 50 50 50 51 53 54 57 59 59 60 60 62 63 63 65 66 69 71 73 76 78 78 78 79 79 79 80 81 81 81 82 82 83 83 85 87 89 91 94 94 94 94 98 99 99 100 100 101 1...

output:

result:

Subtask #5:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Dependency #4:

Subtask #6:

score: 0

Wrong Answer

Test #28:

score: 0

Wrong Answer

time: 1ms

memory: 6000kb

input:

15 0
15 15 15 13 13 13 12 10 10 9 9 6 6 4 2

output:

1 143 8670 293058 6112008 82271448 727061040 220313548 772302705 782736732 722744270 1152986 474266611 766389247 49766400 0

result:

wrong answer 3rd numbers differ - expected: '8673', found: '8670'

Subtask #7:

score: 0

Skipped

Dependency #6:

Subtask #8:

score: 0

Runtime Error

Test #38:

score: 0

Runtime Error

input:

74999 604849250
72634 60382 41531 20689 20667 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...