QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #275853 | #6410. Classical DP Problem | wangqingxian | AC ✓ | 209ms | 199880kb | C++14 | 822b | 2023-12-05 10:01:09 | 2023-12-05 10:01:09 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=(l);i<=(r);++i)
#define mem0(a) memset(a,0,sizeof(a))
#define int long long
using namespace std;
const int N=5e3+10,mod=998244353;
int n,a[N],k,f[N][N],g[N],tim=1,ans=0,temp[N];
void dp(){
For(i,1,n)k=max(k,min(a[i],i));
int t=a[k+1];
f[0][0]=1;
For(i,1,k)
For(j,0,t){
if(j)f[i][j]=f[i-1][j-1]*(t-j+1)%mod;
f[i][j]=(f[i][j]+f[i-1][j]*(a[i]-(t-j))%mod)%mod;
}
ans+=f[k][t];
}
signed main(){
cin>>n;
For(i,1,n){cin>>a[i];temp[i]=a[i];}
reverse(a+1,a+1+n);
dp();mem0(a);
For(i,1,temp[n])For(j,1,n)if(temp[j]>=i) a[i]++;
mem0(f);dp();
For(i,1,k)tim=tim*i%mod;
cout<<k<<" "<<(ans-tim+mod)%mod<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 199776kb
input:
3 1 2 3
output:
2 6
result:
ok 2 number(s): "2 6"
Test #2:
score: 0
Accepted
time: 0ms
memory: 199804kb
input:
1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 7ms
memory: 199784kb
input:
2 1 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #4:
score: 0
Accepted
time: 10ms
memory: 199776kb
input:
2 2 2
output:
2 6
result:
ok 2 number(s): "2 6"
Test #5:
score: 0
Accepted
time: 8ms
memory: 199724kb
input:
3 1 1 1
output:
1 3
result:
ok 2 number(s): "1 3"
Test #6:
score: 0
Accepted
time: 3ms
memory: 199776kb
input:
3 2 2 2
output:
2 9
result:
ok 2 number(s): "2 9"
Test #7:
score: 0
Accepted
time: 0ms
memory: 199720kb
input:
3 3 3 3
output:
3 48
result:
ok 2 number(s): "3 48"
Test #8:
score: 0
Accepted
time: 3ms
memory: 199836kb
input:
5 1 1 3 3 4
output:
3 47
result:
ok 2 number(s): "3 47"
Test #9:
score: 0
Accepted
time: 8ms
memory: 199840kb
input:
10 2 4 5 5 5 5 6 8 8 10
output:
5 864
result:
ok 2 number(s): "5 864"
Test #10:
score: 0
Accepted
time: 24ms
memory: 199728kb
input:
30 6 8 9 9 9 10 13 14 15 15 16 17 17 18 20 22 22 23 23 24 24 25 25 25 27 28 28 29 29 30
output:
17 986189864
result:
ok 2 number(s): "17 986189864"
Test #11:
score: 0
Accepted
time: 12ms
memory: 199776kb
input:
123 1 1 1 2 2 3 3 6 6 7 7 7 8 8 9 9 10 10 10 11 12 12 12 13 14 14 14 14 16 17 17 17 17 17 18 19 20 20 21 21 22 22 22 23 23 23 25 25 26 27 27 28 28 28 28 29 29 30 31 31 31 32 33 33 33 34 35 35 35 36 37 37 38 39 39 39 39 40 41 41 42 42 42 43 44 48 48 50 52 53 55 56 57 57 57 58 65 68 71 74 75 76 76 82 ...
output:
42 287179924
result:
ok 2 number(s): "42 287179924"
Test #12:
score: 0
Accepted
time: 3ms
memory: 199792kb
input:
1234 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 4 5 5 5 5 6 6 7 7 7 7 7 7 7 8 8 8 8 9 9 10 10 10 11 11 11 11 11 12 13 13 14 14 15 15 15 15 16 16 16 17 17 17 18 18 18 19 19 19 19 19 19 19 19 19 19 20 20 20 21 21 21 21 21 22 22 22 23 23 23 23 23 23 23 23 23 24 24 24 24 24 24 24 24 24 24 25 25 25 25 25 26 26 26 26 ...
output:
239 98119841
result:
ok 2 number(s): "239 98119841"
Test #13:
score: 0
Accepted
time: 23ms
memory: 199812kb
input:
2345 1 1 2 2 2 7 7 9 9 9 9 15 17 19 19 22 23 24 25 29 29 29 30 31 32 33 35 37 39 41 42 42 43 43 44 46 46 46 47 48 48 50 51 51 52 53 53 54 55 56 57 58 58 60 61 63 63 64 65 65 65 66 67 67 67 69 69 69 70 71 72 72 73 73 74 75 75 77 77 79 83 85 86 88 90 90 91 93 94 97 99 104 106 107 108 108 109 109 110 1...
output:
1239 588926916
result:
ok 2 number(s): "1239 588926916"
Test #14:
score: 0
Accepted
time: 55ms
memory: 199772kb
input:
3456 4 7 8 8 9 19 20 21 22 23 23 27 29 29 32 32 33 43 45 50 52 52 55 58 58 58 60 62 66 67 68 69 71 74 74 76 77 79 82 82 87 87 88 91 93 95 96 97 99 102 104 106 107 108 121 121 123 126 127 131 137 138 139 142 145 147 152 156 157 159 161 165 166 170 170 172 174 175 178 182 183 185 186 189 190 195 195 1...
output:
2239 24387925
result:
ok 2 number(s): "2239 24387925"
Test #15:
score: 0
Accepted
time: 104ms
memory: 199868kb
input:
4456 4 7 10 10 22 24 29 33 33 34 35 37 40 41 47 48 55 61 61 65 69 71 76 91 95 99 105 105 105 110 112 113 117 117 120 121 122 123 125 127 130 134 135 138 140 141 142 142 144 150 153 154 157 162 165 169 170 170 174 175 176 178 197 198 198 201 208 211 211 212 214 214 215 217 220 224 224 225 230 231 232...
output:
3239 904395650
result:
ok 2 number(s): "3239 904395650"
Test #16:
score: 0
Accepted
time: 170ms
memory: 199752kb
input:
5000 1 5 7 8 24 28 36 47 50 56 59 64 66 85 89 94 95 95 98 108 110 117 122 155 157 158 163 172 172 179 186 197 198 220 236 251 254 254 256 265 287 288 298 302 306 312 327 336 343 344 345 348 350 360 363 364 382 382 390 399 402 406 412 421 425 435 442 445 450 451 453 478 481 490 491 496 499 500 500 50...
output:
4239 328488156
result:
ok 2 number(s): "4239 328488156"
Test #17:
score: 0
Accepted
time: 52ms
memory: 199748kb
input:
5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 ...
output:
5000 317554850
result:
ok 2 number(s): "5000 317554850"
Test #18:
score: 0
Accepted
time: 160ms
memory: 199804kb
input:
5000 4123 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 ...
output:
4999 609985488
result:
ok 2 number(s): "4999 609985488"
Test #19:
score: 0
Accepted
time: 164ms
memory: 199744kb
input:
5000 1501 1689 3190 3774 4708 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 4995 ...
output:
4995 577669110
result:
ok 2 number(s): "4995 577669110"
Test #20:
score: 0
Accepted
time: 209ms
memory: 199756kb
input:
5000 63 107 213 432 444 500 519 543 591 699 704 825 930 1027 1141 1256 1287 1347 1487 1547 1649 1651 1674 1696 1701 1716 1738 1849 1880 1919 1965 1973 1989 2000 2052 2063 2094 2112 2155 2288 2459 2527 2600 2607 2663 2703 2779 2968 3002 3041 3050 3092 3097 3098 3352 3378 3440 3525 3613 3626 3712 3742...
output:
4913 376487851
result:
ok 2 number(s): "4913 376487851"
Test #21:
score: 0
Accepted
time: 207ms
memory: 199880kb
input:
5000 2 9 17 19 50 63 63 82 83 87 92 101 126 136 172 182 187 201 208 214 222 233 242 256 271 272 284 288 294 300 303 323 353 354 418 430 463 500 501 511 543 550 554 568 569 570 570 577 578 590 654 671 680 695 702 705 716 722 732 736 776 783 785 794 797 808 835 855 859 866 891 896 924 934 942 953 961 ...
output:
4567 930123987
result:
ok 2 number(s): "4567 930123987"
Test #22:
score: 0
Accepted
time: 173ms
memory: 199748kb
input:
5000 9 16 18 19 21 27 44 49 53 63 66 70 84 95 95 101 103 107 107 110 113 113 114 118 126 131 132 135 141 155 162 162 162 168 181 183 184 184 190 191 191 194 195 196 201 203 210 210 211 214 215 219 221 222 232 241 243 250 250 252 253 256 258 258 258 263 271 272 274 282 283 287 292 293 296 308 315 317...
output:
4097 266880018
result:
ok 2 number(s): "4097 266880018"
Test #23:
score: 0
Accepted
time: 158ms
memory: 199876kb
input:
5000 1 5 11 11 13 25 41 41 52 55 60 64 65 65 71 77 90 91 92 99 106 109 112 118 120 128 130 135 136 139 148 151 152 152 163 168 170 172 176 178 184 187 191 195 197 198 204 205 206 225 233 234 235 236 242 247 255 256 258 262 263 263 267 271 271 278 288 289 290 296 299 303 304 305 309 311 318 325 341 3...
output:
4096 441159088
result:
ok 2 number(s): "4096 441159088"
Test #24:
score: 0
Accepted
time: 160ms
memory: 199808kb
input:
5000 1 2 9 10 18 19 21 23 24 38 39 39 48 54 58 60 62 66 85 86 91 97 97 103 103 106 109 112 117 122 124 126 148 148 149 152 152 156 158 166 166 172 185 188 190 199 201 202 203 208 208 208 226 232 238 252 258 262 267 280 281 294 295 302 306 307 308 308 309 309 325 329 329 356 366 366 367 373 381 384 3...
output:
4095 288197876
result:
ok 2 number(s): "4095 288197876"
Test #25:
score: 0
Accepted
time: 90ms
memory: 199816kb
input:
5000 1 8 8 12 13 15 19 20 21 22 25 26 31 31 34 35 35 38 40 41 45 48 51 51 52 54 56 57 58 61 62 62 64 64 64 65 67 68 68 68 69 70 74 76 76 76 78 79 79 80 85 86 89 89 90 91 98 101 102 109 110 114 115 115 115 119 120 122 122 126 129 130 131 131 131 134 136 137 139 140 141 142 144 147 150 150 151 152 154...
output:
3123 952629946
result:
ok 2 number(s): "3123 952629946"
Test #26:
score: 0
Accepted
time: 36ms
memory: 199816kb
input:
5000 1 1 1 1 1 2 2 3 3 4 4 4 4 4 4 4 5 5 5 6 6 6 7 7 7 7 7 8 8 9 9 9 9 10 10 10 10 10 11 11 11 11 11 12 12 12 12 13 13 13 14 14 15 15 15 16 16 17 17 17 17 18 18 18 18 18 18 18 18 18 19 19 19 20 20 20 21 21 22 22 22 22 22 22 22 23 23 23 23 24 24 24 24 26 26 26 26 27 27 27 28 28 28 29 29 29 29 30 30 3...
output:
1123 702281788
result:
ok 2 number(s): "1123 702281788"
Test #27:
score: 0
Accepted
time: 16ms
memory: 199864kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4...
output:
123 482123450
result:
ok 2 number(s): "123 482123450"
Test #28:
score: 0
Accepted
time: 11ms
memory: 199744kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...
output:
42 966786798
result:
ok 2 number(s): "42 966786798"
Test #29:
score: 0
Accepted
time: 15ms
memory: 199840kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
13 237554682
result:
ok 2 number(s): "13 237554682"
Test #30:
score: 0
Accepted
time: 12ms
memory: 199752kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
7 5040
result:
ok 2 number(s): "7 5040"
Test #31:
score: 0
Accepted
time: 12ms
memory: 199824kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
5 120
result:
ok 2 number(s): "5 120"
Test #32:
score: 0
Accepted
time: 15ms
memory: 199824kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
3 6
result:
ok 2 number(s): "3 6"
Test #33:
score: 0
Accepted
time: 12ms
memory: 199788kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
2 2
result:
ok 2 number(s): "2 2"
Test #34:
score: 0
Accepted
time: 4ms
memory: 199816kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
1 1
result:
ok 2 number(s): "1 1"
Test #35:
score: 0
Accepted
time: 71ms
memory: 199868kb
input:
5000 1 3 3 3 4 4 5 5 5 5 8 8 8 9 9 9 10 13 14 22 22 22 22 24 24 25 27 28 28 28 32 34 35 35 36 36 38 38 40 41 41 42 46 46 46 47 48 48 48 48 50 52 52 53 55 56 56 57 58 59 60 62 62 63 63 65 67 68 70 72 80 82 83 83 84 86 87 88 89 89 90 91 91 91 92 95 95 96 97 97 100 100 100 100 101 102 104 105 105 107 1...
output:
2496 644254912
result:
ok 2 number(s): "2496 644254912"
Test #36:
score: 0
Accepted
time: 194ms
memory: 199736kb
input:
5000 4999 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 ...
output:
4999 648815172
result:
ok 2 number(s): "4999 648815172"
Test #37:
score: 0
Accepted
time: 202ms
memory: 199820kb
input:
5000 4913 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 4999 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 5000 ...
output:
4999 672978716
result:
ok 2 number(s): "4999 672978716"
Test #38:
score: 0
Accepted
time: 185ms
memory: 199804kb
input:
5000 111 598 627 1600 3510 4414 4855 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 4993 499...
output:
4993 778016618
result:
ok 2 number(s): "4993 778016618"
Test #39:
score: 0
Accepted
time: 190ms
memory: 199812kb
input:
5000 31 56 58 60 100 144 151 166 188 192 249 254 254 254 258 259 308 325 337 355 362 374 424 433 438 451 460 491 491 503 507 513 531 537 539 539 544 566 568 596 605 629 635 636 685 693 702 713 726 735 737 744 754 778 780 781 793 801 811 833 838 838 845 868 876 877 897 923 931 935 951 956 968 978 981...
output:
4712 291142969
result:
ok 2 number(s): "4712 291142969"
Test #40:
score: 0
Accepted
time: 59ms
memory: 199796kb
input:
5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
4712 803514123
result:
ok 2 number(s): "4712 803514123"
Test #41:
score: 0
Accepted
time: 80ms
memory: 199748kb
input:
5000 3 5 6 6 7 7 8 10 10 10 12 12 13 13 13 14 15 16 16 16 16 19 19 20 20 21 23 24 25 26 26 26 27 28 29 30 31 31 32 32 33 33 35 35 37 38 38 39 40 41 41 42 42 42 43 44 46 46 46 48 48 50 51 51 52 52 53 53 53 55 56 57 57 57 59 60 60 62 63 63 64 65 65 67 67 67 69 69 71 71 72 72 72 73 73 74 74 75 76 76 76...
output:
4712 234298773
result:
ok 2 number(s): "4712 234298773"