QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #622876 | #6199. 数圈圈 | zhouhuanyi | 20 | 60ms | 123240kb | C++23 | 985b | 2024-10-09 08:13:19 | 2024-10-09 08:13:19 |
Judging History
answer
#include<iostream>
#include<cstdio>
#define N 7000
#define mod 998244353
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
void Adder(int &x,int d)
{
x=x+d>=mod?x+d-mod:x+d;
return;
}
void Adder2(int &x,int d)
{
x=x+d<0?x+d+mod:x+d;
return;
}
int MD(int x)
{
return x>=mod?x-mod:x;
}
int MD2(int x)
{
return x<0?x+mod:x;
}
int n,y,a[N+1],dp[N+1][N+1];
int main()
{
bool op=1;
n=read(),y=read();
for (int i=1;i<=n;++i) a[i]=read(),op&=(a[i-1]<=a[i]);
if (op)
{
for (int i=1;i<=n;++i)
if (a[i]>=i)
Adder(a[i],y-1);
for (int i=1;i<=n;++i) a[i]=MD2(a[i]-i+1);
dp[0][0]=1;
for (int i=1;i<=n;++i)
for (int j=0;j<=i-1;++j)
{
Adder(dp[i][j+1],dp[i-1][j]);
Adder(dp[i][j],1ll*dp[i-1][j]*MD(a[i]+j)%mod);
}
for (int i=0;i<=n;++i) printf("%d ",dp[n][n-i]);
puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 1ms
memory: 3924kb
input:
1 915080344 1
output:
1 915080344
result:
ok 2 number(s): "1 915080344"
Test #2:
score: 1
Accepted
time: 0ms
memory: 3872kb
input:
1 915080344 0
output:
1 0
result:
ok 2 number(s): "1 0"
Test #3:
score: 1
Accepted
time: 0ms
memory: 3888kb
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: 3828kb
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: 3876kb
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: 3828kb
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: 3948kb
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: 3912kb
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: 3936kb
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: 4040kb
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: 3852kb
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: 3916kb
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: 3856kb
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: 3ms
memory: 19676kb
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: 9ms
memory: 19672kb
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: 9ms
memory: 19692kb
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: 9ms
memory: 19680kb
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: 10ms
memory: 19680kb
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
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 60ms
memory: 123240kb
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:
1 28273340 476873385 642920897 539279528 281671666 45357107 793783035 106890291 529237243 174101931 720557090 438977373 609446719 618618653 277518374 368272731 14456710 397612142 668995173 822948146 676828370 76500142 929921438 710993835 958064207 185024760 419956147 778805309 339659945 883910399 48...
result:
wrong answer 2nd numbers differ - expected: '807105292', found: '28273340'
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
0%
Subtask #6:
score: 0
Wrong Answer
Test #28:
score: 0
Wrong Answer
time: 0ms
memory: 3660kb
input:
15 0 15 15 15 13 13 13 12 10 10 9 9 6 6 4 2
output:
result:
wrong answer Answer contains longer sequence [length = 16], but output contains 0 elements
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Wrong Answer
Test #38:
score: 0
Wrong Answer
time: 0ms
memory: 3680kb
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 ...
output:
result:
wrong answer Answer contains longer sequence [length = 75000], but output contains 0 elements
Subtask #9:
score: 0
Skipped
Dependency #6:
0%