QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#232924	#6410. Classical DP Problem	Ema_nicole	WA	1ms	7700kb	C++14	1.6kb	2023-10-31 01:08:30	2023-10-31 01:08:32

Judging History

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

[2023-10-31 01:08:32]
评测

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

查看

[2023-10-31 01:08:30]
提交

answer

#include <iostream>
#include <algorithm>
#define int long long

using namespace std;
using ll = long long;
const int NMAX = 5002;
const int MOD = 998244353;

int a[NMAX], dp[NMAX][NMAX], n, k, x, m[NMAX][NMAX];

/// k - latura patratului
/// x - coloane inutile

void rotire()
{
    int v[NMAX];
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= a[i]; j++)
            v[j]++;
    }

    for(int i = 1; i <= n; i++)
        a[i] = v[i];
}

int sol()
{
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            dp[i][j] = 0;

    x = a[k + 1];
    dp[0][x] = 1;

    for(int i = 0; i < k; i++)
    {
        for(int j = 0; j <= x; j++)
        {
            dp[i + 1][j] = (dp[i + 1][j] + 1LL * (a[i + 1] - j) * dp[i][j]) % MOD;

            if(j != 0)
                dp[i + 1][j - 1] = (dp[i + 1][j - 1] + 1LL * j * dp[i][j]) % MOD;
        }
    }

    return dp[k][0];
}


signed main()
{
    ll ans = 0, fact = 1;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    reverse(a + 1, a + n + 1);

    /*for(int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << '\n';*/
    for(int i = 1; i <= n; i++)
    {
        if(a[i] >= i)
            k = i;
        else
            break;
    }
    ans = (ans + sol()) % MOD;
    rotire();
    ans = (ans + sol()) % MOD;

    for(ll i = 2; i <= k; i++)
        fact = (1LL * fact * i) % MOD;
    ans = (ans - fact) % MOD;

    cout << k << " " << ans;

    return 0;
}
/*
9
1
1
2
5
5
5
5
7
9

*/

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 5740kb

input:

3
1 2 3

output:

2 6

result:

ok 2 number(s): "2 6"

Test #2:

score: 0

Accepted

time: 1ms

memory: 5688kb

input:

1
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #3:

score: 0

Accepted

time: 1ms

memory: 5684kb

input:

2
1 1

output:

1 2

result:

ok 2 number(s): "1 2"

Test #4:

score: 0

Accepted

time: 1ms

memory: 5680kb

input:

2
2 2

output:

2 6

result:

ok 2 number(s): "2 6"

Test #5:

score: 0

Accepted

time: 1ms

memory: 5752kb

input:

3
1 1 1

output:

1 3

result:

ok 2 number(s): "1 3"

Test #6:

score: 0

Accepted

time: 0ms

memory: 5648kb

input:

3
2 2 2

output:

2 9

result:

ok 2 number(s): "2 9"

Test #7:

score: 0

Accepted

time: 0ms

memory: 5692kb

input:

3
3 3 3

output:

3 48

result:

ok 2 number(s): "3 48"

Test #8:

score: 0

Accepted

time: 1ms

memory: 5780kb

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: 7700kb

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: 5688kb

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 -12054489

result:

wrong answer 2nd numbers differ - expected: '986189864', found: '-12054489'