Submission #754712

#	Time	Username	Problem	Language	Result	Execution time	Memory
754712		Lucpp	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++17	87 / 100	1833 ms	1048576 KiB

festival2

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

int n;
ll mod;

ll power(ll a, ll b){
    ll y = 1;
    while(b){
        if(b & 1) y = y * a % mod;
        b /= 2;
        a = (a*a)%mod;
    }
    return y;
}

ll inv(ll x){
    return power(x, mod-2);
}

struct State{
    int a[2][2][2] = {};
};

void add(int &a, ll x){a = (a+x)%mod;}

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

    vector<vector<State>> dp(2*n+1, vector<State>(n+1));

    dp[0][0].a[0][0][0] = 1;

    for(int i = 1; i <= 2*n; i++){
        for(int k = 0; k <= min(i, n); k++){
            for(int v = 0; v < 2; v++){
                for(int s = 0; s < 2; s++){
                    for(int g = 0; g <= s; g++){
                        int &res = dp[i][k].a[v][s][g];
                        add(res, dp[i-1][k+1].a[v][1][g|(s==0)]);
                        if(s == 1 && g == 1 && v == 0 && k > 0){
                            ll factor = fact[i-1] * inv_fact[i-1-(k-1)] % mod;
                            add(res, dp[i-k][0].a[0][0][0] * factor);
                        }
                        if(s == 1 && g == 0){
                            add(res, dp[i-1][k].a[0][0][0]);
                        }
                        if(k > g && v == 0){
                            ll factor = (k-g) * fact[i-1] % mod * inv_fact[i-1-(k-g-1)] % mod;
                            add(res, dp[i-(k-g)][0].a[1][s][0] * factor);
                        }
                    }
                }
            }
        }
    }
    ll same = dp[2*n][0].a[0][0][0];
    ll total = 1;
    for(int i = 0; i < n; i++) total = total * (2*i+1) % mod;
    // cerr << same << "\n";
    cout << (total - same + mod) % mod << "\n";
}

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