QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#232922	#6410. Classical DP Problem	Ema_nicole	WA	1ms	5612kb	C++14	1.7kb	2023-10-31 01:06:06	2023-10-31 01:06:06

Judging History

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

[2023-10-31 01:06:06]
评测

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

查看

[2023-10-31 01:06:06]
提交

answer

#include <iostream>
#include <algorithm>
#include <vector>

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];
}


int 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;
    //cout << ans << '\n';
    rotire();
    /*for(int i = 1; i <= n; i++)
        cout << a[i] << " ";
    cout << '\n';*/
    ans = (ans + sol()) % MOD;
    //cout << ans << '\n';
    for(int 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

*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5572kb

input:

3
1 2 3

output:

2 6

result:

ok 2 number(s): "2 6"

Test #2:

score: 0

Accepted

time: 1ms

memory: 5456kb

input:

1
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #3:

score: 0

Accepted

time: 1ms

memory: 5412kb

input:

2
1 1

output:

1 2

result:

ok 2 number(s): "1 2"

Test #4:

score: 0

Accepted

time: 0ms

memory: 5416kb

input:

2
2 2

output:

2 6

result:

ok 2 number(s): "2 6"

Test #5:

score: 0

Accepted

time: 1ms

memory: 5612kb

input:

3
1 1 1

output:

1 3

result:

ok 2 number(s): "1 3"

Test #6:

score: 0

Accepted

time: 1ms

memory: 5324kb

input:

3
2 2 2

output:

2 9

result:

ok 2 number(s): "2 9"

Test #7:

score: 0

Accepted

time: 1ms

memory: 5572kb

input:

3
3 3 3

output:

3 48

result:

ok 2 number(s): "3 48"

Test #8:

score: 0

Accepted

time: 1ms

memory: 5572kb

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

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

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'