Submission #1219957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219957		tosivanmak	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++20	87 / 100	9093 ms	1500 KiB

festival2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll MOD;
ll bm(ll a, ll b){
    if(b==0)return 1;
    ll k=bm(a,b/2);
    k*=k; k%=MOD;
    if(b&1)k*=a;
    k%=MOD; return k;
}
ll inv(ll a){
    return bm(a,MOD-2);
}
int dp[2][20005][2][2];
int store_1_1_1[40005],store_0_0_1[40005],store_0_0_0[40005];
ll fact[40005],ifact[40005];
ll tot[2][20005];
/*
    Dimensions:
    1. The position
    2. Number of open brackets
    3. Whether or not the worse strategy has a corresponding open bracket
    4. Delta (better strategy - worse strategy)
*/
void add(int& a, int& b){
    a+=b; a%=MOD;
    // cout<<a<<'\n';
}
int P(int a, int b){
    ll aa=a; ll bb=b;
    ll k=fact[aa]*ifact[aa-bb]%MOD;
    int kk=k;
    return kk;
}
ll C(ll n, ll r){
    return fact[n]*ifact[r]%MOD*ifact[n-r]%MOD;
}
int comb(int a, int b, int c){
    // P(b,c)*a
    int sz=P(b,c);
    // cout<<"P val "<<P(0,0)<<'\n';
    ll ssz=sz; ssz*=a; ssz%=MOD;
    sz=ssz;
    return sz;
}
int mul(ll a, int b){
    a*=b; a%=MOD; a+=MOD; a%=MOD;
    int val=a; return val;
}
string pr(int a, int b, int c, int d){
    string st="dp["+to_string(a)+"]"+"["+to_string(b)+"]"+"["+to_string(c)+"]"+"["+to_string(d)+"]=";
    return st;
}
void solve(){
    ll n;
    cin>>n>>MOD;
    fact[0]=1;
    ifact[0]=1;
    for(int i=1;i<=6000;i++){
        fact[i]=fact[i-1]*i; fact[i]%=MOD;
        ifact[i]=inv(fact[i]);
    }
    dp[0][0][0][0]=1;
    for(int i=0;i<=2*n;i++){
        add(dp[i&1][0][0][0],store_0_0_0[i]);
        add(dp[i&1][0][0][1],store_0_0_1[i]);
        add(dp[i&1][1][1][1],store_1_1_1[i]);
        if(i==2*n)break;
        for(int j=0;j<=n;j++){
            for(int k=0;k<2;k++){
                for(int l=0;l<2;l++){
                    dp[(i+1)&1][j][k][l]=0;
                }
            }
        }
        for(int j=0;j<=n;j++){
           //1. Delta = 1, no corresponding bracket, open bracket for next
        //    add(dp[i+1][j+1][1][1],dp[i][j][0][1]);
           //2. Delta = 1, no corresponding bracket, close bracket for next, Impossible
           //3. Delta = 1, have corresponding bracket, open bracket for next
           add(dp[(i+1)&1][j+1][1][1],dp[i&1][j][1][1]);
           //4. Delta = 1, have corresponding bracket, close bracket for next
           if(j!=0)add(dp[(i+1)&1][j-1][0][0],dp[i&1][j][1][1]);
           //5. Delta = 0, no corresponding bracket, open bracket for next
           add(dp[(i+1)&1][j+1][1][0],dp[i&1][j][0][0]);
           //6. Delta = 0, no corresponding bracket, close bracket for next
        //    if(j!=0)add(dp[i+1][j-1][0][1],dp[i][j][0][0]); // Need speed up
           if(i+j<=2*n&&j!=0){
               ll val=comb(dp[i&1][j][0][0],2*n-(i+1),j-1);
               int rb=mul(val,j);
               add(store_0_0_1[i+j],rb);
           }
           //7. Delta = 0, have corresponding bracket, open bracket for next
           add(dp[(i+1)&1][j+1][1][0],dp[i&1][j][1][0]);
           //8. Delta = 0, have corresponding bracket, close bracket for next
           // Case 1: Close for both worse and better
        //    if(j!=0)add(dp[i+1][j-1][0][0],dp[i][j][1][0]); // Need speed up
            if(i+j<=2*n&&j!=0){
               int val=comb(dp[i&1][j][1][0],2*n-(i+1),j-1);
            //    cout<<i<<" "<<j<<" "<<1<<' '<<0<<" "<<2*n-(i+1)<<" "<<j-1<<' '<<val<<'\n';
               add(store_0_0_0[i+j],val);
           }
           // Case 2: Close for only the better
        //    if(j!=0)add(dp[i+1][j-1][1][1],dp[i][j][1][0]); // Need speed up
           if(i+j-1<=2*n&&j>1){
               ll val=comb(dp[i&1][j][1][0],2*n-(i+1),j-2);
               int rb=mul(val,j-1);
               add(store_1_1_1[i+j-1],rb);
           }
        }
    }
    // for(int i=1;i<=2*n;i++){
    //     for(int j=0;j<=n;j++){
    //         cout<<pr(i,j,0,0)<<dp[i][j][0][0]<<" "<<pr(i,j,0,1)<<dp[i][j][0][1]<<' '<<pr(i,j,1,0)<<dp[i][j][1][0]<<' '<<pr(i,j,1,1)<<dp[i][j][1][1]<<'\n';
    //     }
    //     cout<<'\n';
    // }
    // dp[2][0][0][0]=1, dp[2][2][1][0]=1
    // dp[3][1][1][0]=1, dp[3][1][1][1]=1, dp[3][3][1][0]=1, 
    for(int i=0;i<2;i++){
        for(int j=0;j<n+5;j++)tot[i][j]=0;
    }
    tot[0][0]=1;
    for(int i=1;i<=2*n;i++){
        for(int j=0;j<=n;j++){
            tot[i&1][j]=0;
            if(j!=0)tot[i&1][j]=tot[(i-1)&1][j-1];
            tot[i&1][j]+=(tot[(i-1)&1][j+1]*(j+1)%MOD); tot[i&1][j]%=MOD;
        }
    }
    ll totals=tot[(2*n)&1][0];
    totals-=(dp[(2*n)&1][0][0][0]+dp[(2*n)&1][0][1][0]);
    totals%=MOD; totals+=MOD; totals%=MOD;
    cout<<totals<<'\n';
}
int32_t main(){
    // freopen("debug.txt","w",stdout);
    ll t=1;
    // cin>>t;
    while(t--)solve();
}

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