oj.uz

Submission #898261

# Submission time Handle Problem Language Result Execution time Memory
898261 2024-01-04T12:15:27 Z LucaIlie Festivals in JOI Kingdom 2 (JOI23_festival2) C++17
10 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int MAX_N = 3000;
const int MAX_FACT = 3 * MAX_N;
int mod;
int fact[MAX_FACT + 1], invFact[MAX_FACT + 1], countB[MAX_N + 1], countBU[MAX_N + 1];

int lgPut( int x, int n ) {
    if ( n == 0 )
        return 1;

    int p = lgPut( x, n / 2 );
    p = (long long)p * p % mod;
    if ( n % 2 == 1 )
        p = (long long)p * x % mod;

    return p;
}

void initFact( int n ) {
    fact[0] = 1;
    for ( int i = 1; i <= n; i++ )
        fact[i] = (long long)fact[i - 1] * i % mod;
    invFact[n] = lgPut( fact[n], mod - 2 );
    for ( int i = n - 1; i >= 0; i-- )
        invFact[i] = (long long)invFact[i + 1] * (i + 1) % mod;
}

int comb( int n, int k ) {
    return (long long)fact[n] * invFact[n - k] % mod * invFact[k];
}

int prodCons( int x, int k ) {
    if ( x < 0 )
        return 1;
    if ( x == 0 )
        return fact[x + k - 1];
    return (long long)fact[x + k - 1] * invFact[x - 1] % mod;
}

signed main() {
    int n;

    cin >> n >> mod;

    initFact( 3 * n );


    countB[2] = 1;
    countBU[1] = 1;
    for ( int i = 1; i <= n; i++ ) {
        //B<--B 1
        for ( int k = 0; i + k + 2 <= n; k++ )
            countB[i + k + 2] = (countB[i + k + 2] + (long long)countB[i] * comb( k + 2, 2 ) % mod * prodCons( 2 * i - 2, k ) % mod) % mod;

        //B<--B 2
        for ( int k = 0; i + k + 2 <= n; k++ )
            countB[i + k + 2] = (countB[i + k + 2] + (long long)countB[i] * comb( k + 2, 2 ) % mod * prodCons( 2 * i - 2, k ) % mod) % mod;

        //B<--BU
        for ( int k = 0; i + k + 2 <= n; k++ )
            countB[i + k + 2] = (countB[i + k + 2] + (long long)countBU[i] * (k + 1) % mod * prodCons( 2 * i - 1, k ) % mod) % mod;

        //BU<--B
        for ( int k = 0; i + k + 1 <= n; k++ )
            countBU[i + k + 1] = (countBU[i + k + 1] + (long long)countB[i] * (k + 1) % mod * prodCons( 2 * i - 2, k ) % mod) % mod;

        //BU<--BU
        for ( int k = 0; i + k + 1 <= n; k++ )
            countBU[i + k + 1] = (countBU[i + k + 1] + (long long)countBU[i] * prodCons( 2 * i - 1, k ) % mod) % mod;
    }

    int tot = 1;
    for ( int i = 3; i < 2 * n; i += 2 )
        tot = (long long)tot * i % mod;

    int correct = 0;
    for ( int i = 1; i <= n; i++ ) {
        int k = n - i;
        correct = (correct + (long long)countB[i] * (k + 1) % mod * prodCons( 2 * i - 2, k ) % mod) % mod;
        correct = (correct + (long long)countBU[i] * prodCons( 2 * i - 1, k ) % mod) % mod;
    }

    cout << (tot - correct + mod) % mod;

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -