QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#232902	#6410. Classical DP Problem	ksun	WA	1ms	7484kb	C++14	1.3kb	2023-10-31 00:27:42	2023-10-31 00:27:42

Judging History

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

[2023-10-31 00:27:42]
评测

测评结果：WA
用时：1ms
内存：7484kb

查看

[2023-10-31 00:27:42]
提交

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=a[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]+=dp1[i][j]*(a[i+1]-j);
        }
    }
    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]+=dp2[i][j]*(a[i+1]-j);
        }
    }
    cout<<k<<" "<<dp1[k][0]+dp2[k][0]-factorial(k);
    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 5456kb

input:

3
1 2 3

output:

2 6

result:

ok 2 number(s): "2 6"

Test #2:

score: 0

Accepted

time: 0ms

memory: 5620kb

input:

1
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #3:

score: 0

Accepted

time: 1ms

memory: 5460kb

input:

2
1 1

output:

1 2

result:

ok 2 number(s): "1 2"

Test #4:

score: 0

Accepted

time: 0ms

memory: 5444kb

input:

2
2 2

output:

2 6

result:

ok 2 number(s): "2 6"

Test #5:

score: 0

Accepted

time: 0ms

memory: 5460kb

input:

3
1 1 1

output:

1 3

result:

ok 2 number(s): "1 3"

Test #6:

score: 0

Accepted

time: 1ms

memory: 5456kb

input:

3
2 2 2

output:

2 9

result:

ok 2 number(s): "2 9"

Test #7:

score: 0

Accepted

time: 1ms

memory: 5464kb

input:

3
3 3 3

output:

3 48

result:

ok 2 number(s): "3 48"

Test #8:

score: 0

Accepted

time: 0ms

memory: 7484kb

input:

5
1 1 3 3 4

output:

3 47

result:

ok 2 number(s): "3 47"

Test #9:

score: 0

Accepted

time: 1ms

memory: 5628kb

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: -100

Wrong Answer

time: 1ms

memory: 5452kb

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:

18 1114368711443504449

result:

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