Submission #898370

#	Time	Username	Problem	Language	Result	Execution time	Memory
898370		LucaIlie	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++17	100 / 100	6612 ms	1364 KiB

festival2

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

const int MAX_N = 20000;
const int MAX_FACT = 2 * 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;
}

inline int prod( int a, int b ) {
    int ret = (long long)a * b - (long long)mod * ((long long)(1.0 / mod * a * b));
    return ret + mod * (ret < 0) - mod * (ret >= (long long)mod);
}

inline int prodCons( int x, int k ) {
    if ( x < 0 )
        return 1;
    if ( x == 0 )
        return fact[x + k - 1];
    return prod( fact[x + k - 1], invFact[x - 1] );
}

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++ ) {
        for ( int k = 0; i - k - 1 >= 1; k++ ) {
            //B<--B
            countB[i] += prod( prod( countB[i - k - 2], (k + 1) * (k + 2) / 2 ), prodCons( 2 * (i - k - 2) - 2, k ) ) * 2 % mod;
            countB[i] = (countB[i] >= mod ? countB[i] - mod : countB[i]);
            //B<--BU
            countB[i] += prod( prod( countBU[i - k - 2], k + 1 ), prodCons( 2 * (i - k - 2) - 1, k ) );
            countB[i] = (countB[i] >= mod ? countB[i] - mod : countB[i]);
            //BU<--B
            countBU[i] += prod( prod( countB[i - k - 1], k + 1 ), prodCons( 2 * (i - k - 1) - 2, k ) );
            countBU[i] = (countBU[i] >= mod ? countBU[i] - mod : countBU[i]);
            //BU<--BU
            countBU[i] += prod( countBU[i - k - 1], prodCons( 2 * (i - k - 1) - 1, k ) );
            countBU[i] = (countBU[i] >= mod ? countBU[i] - mod : countBU[i]);
        }
    }

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

    cout << tot;

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 27 / 27
• Subtask 4: 14 / 14
• Subtask 5: 36 / 36
• Subtask 6: 13 / 13