QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #559499 | #6410. Classical DP Problem | mjkim112358 | TL | 669ms | 47188kb | Python3 | 816b | 2024-09-11 22:33:32 | 2024-09-11 22:33:32 |
Judging History
answer
mod=998244353
def solve(li,k):
if(len(li)==k):
ret=1
for i in li:ret*=i;ret%=mod
return ret
dp=[[0]*(li[k]+1) for i in range(k+1)]
dp[0][0]=1
for i in range(1,k+1):
dp[i][0]=dp[i-1][0]*((li[i-1]-li[k]))
dp[i][0]%=mod
for j in range(1,li[k]+1):
dp[i][j]=dp[i-1][j]*(j+(li[i-1]-li[k]))+dp[i-1][j-1]*(li[k]-(j-1))
dp[i][j]%=mod
return dp[k][li[k]]
n=int(input())
l=list(map(int,input().split()))[::-1]+[0]
#l의 차를 구한 수열
l2=[l[i]-l[i+1] for i in range(n)]
l3=[]
for i in range(n):l3+=[n-i]*l2[n-i-1]
r=l[0]
for i in range(n):
if(l[i]>=i+1):r=i+1
if(l[i]<i+1):break
ans1=solve(l[:-1],r)
ans2=solve(l3,r)
f=1
for i in range(1,r+1):
f*=i
f%=mod
print(r,(ans1+ans2-f)%mod)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 10704kb
input:
3 1 2 3
output:
2 6
result:
ok 2 number(s): "2 6"
Test #2:
score: 0
Accepted
time: 11ms
memory: 10744kb
input:
1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 14ms
memory: 10640kb
input:
2 1 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #4:
score: 0
Accepted
time: 14ms
memory: 10676kb
input:
2 2 2
output:
2 6
result:
ok 2 number(s): "2 6"
Test #5:
score: 0
Accepted
time: 11ms
memory: 10524kb
input:
3 1 1 1
output:
1 3
result:
ok 2 number(s): "1 3"
Test #6:
score: 0
Accepted
time: 0ms
memory: 10580kb
input:
3 2 2 2
output:
2 9
result:
ok 2 number(s): "2 9"
Test #7:
score: 0
Accepted
time: 5ms
memory: 10716kb
input:
3 3 3 3
output:
3 48
result:
ok 2 number(s): "3 48"
Test #8:
score: 0
Accepted
time: 14ms
memory: 10648kb
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: 10604kb
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: 8ms
memory: 10720kb
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: 6ms
memory: 10708kb
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: 35ms
memory: 11908kb
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: 669ms
memory: 47188kb
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: -100
Time Limit Exceeded
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...