QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#559487	#6410. Classical DP Problem	mjkim112358	WA	13ms	10716kb	Python3	754b	2024-09-11 22:24:23	2024-09-11 22:24:24

Judging History

你现在查看的是最新测评结果

[2024-09-11 22:24:24]
评测

测评结果：WA
用时：13ms
内存：10716kb

查看

[2024-09-11 22:24:23]
提交

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]=1
        for j in range(1,li[k]+1):
            dp[i][j]=dp[i-1][j]*(j+(li[i-1]-k))+dp[i-1][j-1]*(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=1
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)

源文件, 语言: Python3

詳細信息

Test #1:

score: 100

Accepted

time: 6ms

memory: 10704kb

input:

3
1 2 3

output:

2 6

result:

ok 2 number(s): "2 6"

Test #2:

score: 0

Accepted

time: 9ms

memory: 10716kb

input:

1
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #3:

score: 0

Accepted

time: 12ms

memory: 10644kb

input:

2
1 1

output:

1 2

result:

ok 2 number(s): "1 2"

Test #4:

score: -100

Wrong Answer

time: 13ms

memory: 10604kb

input:

2
2 2

output:

1 998244352

result:

wrong answer 1st numbers differ - expected: '2', found: '1'