QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #232911 | #6410. Classical DP Problem | ksun | RE | 100ms | 320820kb | C++14 | 1.6kb | 2023-10-31 00:33:43 | 2023-10-31 00:33:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long n,a[5001],k,x,dp1[5001][5001],dp2[5001][5001],v[5001];
long long factorial(long long n)
{
long long nr=1;
for(long long i=1;i<=n;i++)
nr=(nr*i)%mod;
return nr;
}
void rotire()
{
for(long long i=1;i<=n;i++)
{
long long j=1;
while(j<=n and a[j]>=i)
j++;
v[i]=j-1;
}
for(int i=1;i<=n;i++)
a[i]=v[i];
}
int main()
{
cin>>n;
for(long long i=1;i<=n;i++)
cin>>a[i];
reverse(a+1,a+n+1);
for(long long i=1;i<=n;i++)
{
if(a[i]>=i)
k=i;
else
break;
}
x=a[k+1];
dp1[0][x]=1;
for(long long i=0;i<=k;i++)
{
for(long long j=0;j<=x;j++)
{
if(j>0)
{
dp1[i+1][j-1]+=dp1[i][j]*j;
dp1[i+1][j-1]%=mod;
}
dp1[i+1][j]+=dp1[i][j]*(a[i+1]-j);
dp1[i+1][j]%=mod;
}
}
rotire();
x=a[k+1];
dp2[0][x]=1;
for(long long i=0;i<=k;i++)
{
for(long long j=0;j<=x;j++)
{
if(j>0)
{
dp2[i+1][j-1]+=dp2[i][j]*j;
dp2[i+1][j-1]%=mod;
}
dp2[i+1][j]+=dp2[i][j]*(a[i+1]-j);
dp2[i+1][j]%=mod;
}
}
long long total=0;
total=dp1[k][0]+dp2[k][0]-factorial(k);
total%=mod;
while(total<0)
total+=mod;
cout<<k<<" "<<total;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5680kb
input:
3 1 2 3
output:
2 6
result:
ok 2 number(s): "2 6"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5732kb
input:
1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5632kb
input:
2 1 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 5736kb
input:
2 2 2
output:
2 6
result:
ok 2 number(s): "2 6"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5668kb
input:
3 1 1 1
output:
1 3
result:
ok 2 number(s): "1 3"
Test #6:
score: 0
Accepted
time: 0ms
memory: 5684kb
input:
3 2 2 2
output:
2 9
result:
ok 2 number(s): "2 9"
Test #7:
score: 0
Accepted
time: 1ms
memory: 7716kb
input:
3 3 3 3
output:
3 48
result:
ok 2 number(s): "3 48"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5768kb
input:
5 1 1 3 3 4
output:
3 47
result:
ok 2 number(s): "3 47"
Test #9:
score: 0
Accepted
time: 0ms
memory: 5684kb
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: 0ms
memory: 5700kb
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: 0ms
memory: 5932kb
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: 8452kb
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: 12ms
memory: 39276kb
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: 40ms
memory: 101080kb
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: 72ms
memory: 194692kb
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: 100ms
memory: 320820kb
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: -100
Runtime Error
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 ...