QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#232889	#6410. Classical DP Problem	elisaipate	WA	1ms	7640kb	C++14	1.0kb	2023-10-31 00:14:31	2023-10-31 00:14:31

Judging History

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

[2023-10-31 00:14:31]
评测

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

查看

[2023-10-31 00:14:31]
提交

answer

#include <iostream>

using namespace std;
#define nmax 5001
#define mod 998244353


int lin[nmax], col[nmax];
long long dp[2][nmax][nmax], n, k;

void fctdp( int ind, int a[] ) {
    int i, j;
    for( i = 0; i < k; i++ ) {
        for( j = 0; j < k+1; j++ ) {
            dp[ind][i+1][j] +=  (long long)(a[i+1] - j) * dp[ind][i][j] % mod;
            if( j >= 1 )
                dp[ind][i+1][j-1] += (long long)j * dp[ind][i][j] % mod;
        }
    }
}


int main()
{
    int i, j;
    long long fact;
    cin >> n;
    for( i = n; i >= 1; i-- )
        cin >> lin[i];

    for( i = 1; i <= n; i++) {
        for( j = 1; j <= lin[i]; j++ )
            col[j]++;
    }

    k = 1;
    while( lin[k] >= k )
        k++;
    k--;


    dp[0][0][lin[k+1]] = 1;

    dp[1][0][col[k+1]] = 1;


    fctdp( 0, lin );
    fctdp( 1, col );



    fact = 1;
    for( i = 2; i <= k; i++ )
        fact = (long long) fact * i % mod;

    cout << k << " " << dp[0][k][0] + dp[1][k][0] - fact;

    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5752kb

input:

3
1 2 3

output:

2 6

result:

ok 2 number(s): "2 6"

Test #2:

score: 0

Accepted

time: 1ms

memory: 5608kb

input:

1
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #3:

score: 0

Accepted

time: 1ms

memory: 5620kb

input:

2
1 1

output:

1 2

result:

ok 2 number(s): "1 2"

Test #4:

score: 0

Accepted

time: 1ms

memory: 5592kb

input:

2
2 2

output:

2 6

result:

ok 2 number(s): "2 6"

Test #5:

score: 0

Accepted

time: 0ms

memory: 5748kb

input:

3
1 1 1

output:

1 3

result:

ok 2 number(s): "1 3"

Test #6:

score: 0

Accepted

time: 1ms

memory: 7640kb

input:

3
2 2 2

output:

2 9

result:

ok 2 number(s): "2 9"

Test #7:

score: 0

Accepted

time: 1ms

memory: 5696kb

input:

3
3 3 3

output:

3 48

result:

ok 2 number(s): "3 48"

Test #8:

score: 0

Accepted

time: 1ms

memory: 5728kb

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

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

Accepted

time: 1ms

memory: 5648kb

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 986189864

result:

ok 2 number(s): "17 986189864"

Test #11:

score: -100

Wrong Answer

time: 1ms

memory: 6008kb

input:

123
1 1 1 2 2 3 3 6 6 7 7 7 8 8 9 9 10 10 10 11 12 12 12 13 14 14 14 14 16 17 17 17 17 17 18 19 20 20 21 21 22 22 22 23 23 23 25 25 26 27 27 28 28 28 28 29 29 30 31 31 31 32 33 33 33 34 35 35 35 36 37 37 38 39 39 39 39 40 41 41 42 42 42 43 44 48 48 50 52 53 55 56 57 57 57 58 65 68 71 74 75 76 76 82 ...

output:

42 1285424277

result:

wrong answer 2nd numbers differ - expected: '287179924', found: '1285424277'