Submission #749212

#	Time	Username	Problem	Language	Result	Execution time	Memory
749212		Lucpp	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++17	37 / 100	9016 ms	1748 KiB

festival2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie();
    int n; ll mod;
    cin >> n >> mod;
    vector<vector<ll>> binom(n+1, vector<ll>(n+1));
    for(int i = 0; i <= n; i++){
        binom[i][0] = 1;
        for(int j = 1; j <= i; j++){
            binom[i][j] = (binom[i-1][j-1] + binom[i-1][j]) % mod;
        }
    }
    vector<ll> fact(n+1);
    fact[0] = 1;
    for(int i = 1; i <= n; i++) fact[i] = (fact[i-1]*i) % mod;

    vector<vector<ll>> dp(n+1, vector<ll>(n+1));
    dp[n][n] = 1;
    for(int a = n-1; a >= 0; a--){
        for(int b = a; b >= 0; b--){
            ll res = 0;
            for(int k = a+1; k <= n; k++){
                for(int l = a+1; l <= k; l++){
                    ll cnt = 0;
                    if(k == l){
                        for(int e = 1; e <= l-b; e++){
                            ll add = binom[l-b-1][e-1] * fact[e] % mod;
                            for(int up = 0; up < l-b-e; up++){
                                add = add * (2*(n-l)+up) % mod;
                            }
                            cnt = (cnt + add) % mod;
                            // cerr << "# " << binom[l-b][e-1] << " " << fact[e] << "\n";
                        }
                    }
                    else
                    for(int ek = 1; ek <= l-b; ek++){
                        for(int el = 1; ek+el <= l-b; el++){
                            ll add = binom[l-b-1][ek+el-1] * binom[ek+el-1][el] % mod;
                            add = add * fact[ek] % mod;
                            add = add * fact[el] % mod;
                            for(int up = 0; up < l-b-el-ek; up++){
                                add = add * (2*(n-l)-1+up) % mod;
                            }
                            cnt = (cnt + add) % mod;
                        }
                    }
                    res = (res + cnt * dp[k][l]) % mod;
                    // cerr << a << " " << b << " " << k << " " << l << "  ->  " << cnt << " " << cnt*dp[k][l] << "\n";
                }
            }
            dp[a][b] = res;
        }
    }
    ll total = 1;
    for(int i = 0; i < n; i++) total = total * (2*i+1) % mod;
    // cerr << dp[0][0] << "\n";
    cout << (total - dp[0][0] + mod) % mod << "\n";
}

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