QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #750082 | #6199. 数圈圈 | jason_sun | 20 | 18ms | 35240kb | C++14 | 1.8kb | 2024-11-15 12:33:55 | 2024-11-15 12:33:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2005, mod=998244353;
void add(ll &x, ll y){
x=(x+y)%mod;
}
int a[N], b[N];
ll f[N][N];
ll qp(ll x, ll y){
ll ans=1;
for(;y;y/=2,x=x*x%mod){
if(y&1) ans=ans*x%mod;
}
return ans;
}
int main(){
// freopen("story.in", "r", stdin);
// freopen("story.out", "w", stdout);
int n, y;
scanf("%d%d", &n, &y);
for(int i=1; i<=n; ++i){
scanf("%d", &a[i]);
}
for(int i=1; i<=n; ++i){
b[i]=b[i-1];
while(b[i]<n&&a[b[i]+1]>=i) b[i]++;
}
if(a[1]<=a[n]){
f[0][0]=1;
for(int i=1; i<=n; ++i){
if(a[i]>=i){
for(int j=0; j<=n; ++j){
add(f[i][j], f[i-1][j]);
add(f[i][j+1], f[i-1][j]*(a[i]-1-j));
add(f[i][j+1], f[i-1][j]*y);
}
}else{
for(int j=0; j<=n; ++j){
add(f[i][j], f[i-1][j]);
add(f[i][j+1], f[i-1][j]*(a[i]-j));
}
}
}
for(int i=0; i<=n; ++i){
printf("%lld%c", f[n][i], " \n"[i==n]);
}
}else{
f[n+1][0]=1;
for(int i=n; i>=1; --i){
if(a[i]>=i){
// if(a[i]>=b[i]){
for(int j=0; j<=n; ++j){
add(f[i][j], f[i+1][j]);
add(f[i][j+1], f[i+1][j]*(a[i]-1+y-j));
}
// }else{
// ll t=(b[i]-a[i]+1)*qp(b[i]-i+1, mod-2)%mod;
// for(int j=0; j<=n; ++j){
// add(f[i][j], f[i+1][j]);
// add(f[i][j+1], f[i+1][j]*(a[i]-j+(y-1)*t%mod));
// }
// }
}else{
for(int j=0; j<=n; ++j){
add(f[i][j], f[i+1][j]);
add(f[i][j+1], f[i+1][j]*(a[i]-j));
}
}
}
for(int i=0; i<=n; ++i){
printf("%lld%c", f[1][i], " \n"[i==n]);
}
}
return 0;
}
//6 3 1
//3 2 2
//
//0 0 1 : 1
//2 0 1 : 1
//3 0 1 : y
//0 2 1 : y
//3 2 1 : y^2
//
//0 0 2 : 1
//1 0 2 : y
//3 0 2 : 1
//0 1 2 : 1
//3 1 2 : y
/*
6 4 1
4 2 2 2
5 5 3 3 1
5 4 4 2 2
*/
詳細信息
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: 3916kb
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: 3924kb
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: 3912kb
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: 3888kb
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: 3924kb
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: 3872kb
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: 3888kb
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: 3980kb
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: 3876kb
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: 3968kb
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: 3960kb
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: 14ms
memory: 35240kb
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: 7ms
memory: 35184kb
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: 12ms
memory: 35228kb
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: 16ms
memory: 35208kb
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: 18ms
memory: 35092kb
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:
0%
Subtask #6:
score: 0
Wrong Answer
Test #28:
score: 0
Wrong Answer
time: 0ms
memory: 3872kb
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:
0%
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 ...
output:
result:
Subtask #9:
score: 0
Skipped
Dependency #6:
0%