oj.uz

Submission #898341

# Submission time Handle Problem Language Result Execution time Memory
898341 2024-01-04T14:09:15 Z LucaIlie Festivals in JOI Kingdom 2 (JOI23_festival2) C++17
0 / 100
 2 ms 860 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 20000;
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] % mod;
}

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

int main() {
    int n;

    cin >> n >> mod;

    initFact( MAX_FACT );

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

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

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

        //BU<--BU
        for ( int k = 0; i - k - 1 >= 1; k++ )
            countBU[i] = (countBU[i] + (long long)countBU[i - k - 1] * prodCons( 2 * (i - k - 1) - 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Incorrect 2 ms 860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Incorrect 2 ms 860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Incorrect 2 ms 860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Incorrect 2 ms 860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Incorrect 2 ms 860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Incorrect 2 ms 860 KB Output isn't correct
3 Halted 0 ms 0 KB -