QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #559495 | #6410. Classical DP Problem | mjkim112358 | WA | 15ms | 10740kb | Python3 | 815b | 2024-09-11 22:31:01 | 2024-09-11 22:31:01 |
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-1):
if(l[i]>=i+1 and l[i+1]<i+1):r=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: 5ms
memory: 10740kb
input:
3 1 2 3
output:
2 6
result:
ok 2 number(s): "2 6"
Test #2:
score: 0
Accepted
time: 14ms
memory: 10624kb
input:
1 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #3:
score: 0
Accepted
time: 9ms
memory: 10612kb
input:
2 1 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #4:
score: 0
Accepted
time: 5ms
memory: 10604kb
input:
2 2 2
output:
2 6
result:
ok 2 number(s): "2 6"
Test #5:
score: 0
Accepted
time: 15ms
memory: 10700kb
input:
3 1 1 1
output:
1 3
result:
ok 2 number(s): "1 3"
Test #6:
score: 0
Accepted
time: 12ms
memory: 10704kb
input:
3 2 2 2
output:
2 9
result:
ok 2 number(s): "2 9"
Test #7:
score: 0
Accepted
time: 11ms
memory: 10556kb
input:
3 3 3 3
output:
3 48
result:
ok 2 number(s): "3 48"
Test #8:
score: 0
Accepted
time: 8ms
memory: 10580kb
input:
5 1 1 3 3 4
output:
3 47
result:
ok 2 number(s): "3 47"
Test #9:
score: -100
Wrong Answer
time: 14ms
memory: 10704kb
input:
10 2 4 5 5 5 5 6 8 8 10
output:
10 17904000
result:
wrong answer 1st numbers differ - expected: '5', found: '10'