제출 #1131221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131221		huutuan	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++20	37 / 100	1733 ms	83936 KiB

festival2

#include <bits/stdc++.h>

using namespace std;

const int N=110;
int n, mod, f[N*2][N][N][2][2][2], g[N*2][N];

void add(int &x, int y){
   x=x+y>=mod?x+y-mod:x+y;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> mod;
   // int ans=0;
   g[n*2][0]=1;
   for (int i=n*2; i>=1; --i) for (int j=n; j>=0; --j){
      { // add (
         if (j) add(g[i-1][j-1], g[i][j]);
      }
      { // add )
         add(g[i-1][j+1], 1ll*g[i][j]*(j+1)%mod);
      }
   }
   // k: so cai mo ngoac dung sau cai cuoi cung cua type 2
   f[0][0][0][0][0][0]=1;
   for (int i=0; i<n*2; ++i) for (int j=0; j<=n; ++j) for (int k=0; k<=n; ++k) for (int d=0; d<2; ++d){
      // cai ngoac cua type 1 co dung truoc cai cuoi cung duoc match cua type 2 khong
      // dung truoc / khong co = 0
      // dung sau = 1
      { // add (
         // la cai dau tien
         add(f[i+1][j][k][d][1][1], f[i][j][k][d][0][0]);
         // khong phai cai dau tien
         add(f[i+1][j+1][k+1][d][0][1], f[i][j][k][d][0][1]);
         add(f[i+1][j+1][k+1][d][1][1], f[i][j][k][d][1][1]);
      }
      { // add )
         // match voi cai ngoac cua type 1
         // case 1: dung truoc
         if (d) add(f[i+1][j][k][d-1][0][0], f[i][j][k][d][0][1]);
         // case 2: dung sau
         add(f[i+1][j][0][d][0][0], f[i][j][k][d][1][1]);
         // khong match voi type 1
         if (j){
            // case 1: dung truoc
            add(f[i+1][j-1][k][d][0][0], 1ll*f[i][j][k][d][0][0]*(j-k)%mod);
            add(f[i+1][j-1][k][d][0][1], 1ll*f[i][j][k][d][0][1]*(j-k)%mod);
            add(f[i+1][j-1][k][d][1][1], 1ll*f[i][j][k][d][1][1]*(j-k)%mod);
            // case 2: dung sau
            if (d==0){
               add(f[i+1][j-1][0][d+1][0][0], 1ll*f[i][j][k][d][0][0]*k%mod);
               add(f[i+1][j-1][0][d+1][0][1], 1ll*f[i][j][k][d][0][1]*k%mod);
               add(f[i+1][j-1][0][d+1][0][1], 1ll*f[i][j][k][d][1][1]*k%mod);
            }else{
               // ans+=f[i][j][k][d][0][0]*k*g[i+1][j-1];
               // ans+=f[i][j][k][d][0][1]*k*g[i+1][j];
               // ans+=f[i][j][k][d][1][1]*k*g[i+1][j];
            }
         }
      }
   }
   // ans+=f[n*2][0][0][1][0][0];
   // cout << ans << '\n';
   // cout << g[0][0] << '\n';
   // cout << f[n*2][0][0][0][0][0] << '\n';
   cout << (g[0][0]-f[n*2][0][0][0][0][0]+mod)%mod << '\n';
   return 0;
}

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