제출 #1131223

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

festival2

#include <bits/stdc++.h>

using namespace std;

const int N=310;
int n, mod, f[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){
      memset(f[(i+1)&1], 0, sizeof f[(i+1)&1]);
      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)&1][j][k][d][1][1], f[i&1][j][k][d][0][0]);
            // khong phai cai dau tien
            add(f[(i+1)&1][j+1][k+1][d][0][1], f[i&1][j][k][d][0][1]);
            add(f[(i+1)&1][j+1][k+1][d][1][1], f[i&1][j][k][d][1][1]);
         }
         { // add )
            // match voi cai ngoac cua type 1
            // case 1: dung truoc
            if (d) add(f[(i+1)&1][j][k][d-1][0][0], f[i&1][j][k][d][0][1]);
            // case 2: dung sau
            add(f[(i+1)&1][j][0][d][0][0], f[i&1][j][k][d][1][1]);
            // khong match voi type 1
            if (j){
               // case 1: dung truoc
               add(f[(i+1)&1][j-1][k][d][0][0], 1ll*f[i&1][j][k][d][0][0]*(j-k)%mod);
               add(f[(i+1)&1][j-1][k][d][0][1], 1ll*f[i&1][j][k][d][0][1]*(j-k)%mod);
               add(f[(i+1)&1][j-1][k][d][1][1], 1ll*f[i&1][j][k][d][1][1]*(j-k)%mod);
               // case 2: dung sau
               if (d==0){
                  add(f[(i+1)&1][j-1][0][d+1][0][0], 1ll*f[i&1][j][k][d][0][0]*k%mod);
                  add(f[(i+1)&1][j-1][0][d+1][0][1], 1ll*f[i&1][j][k][d][0][1]*k%mod);
                  add(f[(i+1)&1][j-1][0][d+1][0][1], 1ll*f[i&1][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[0][0][0][0][0][0]+mod)%mod << '\n';
   return 0;
}

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