[UCPC 2023 예비소집] 계단 자르기

지문이 짧길래 저번에 카페에서 떠들다가 핸드폰 메모장을 이용해서 대충 풀이를 내봤는데 흥미로웠다.

어제 메모장 정리하다 메모를 발견해서 구현해보았다.

 

일단 문제 자체가 너무 점화식으로 잘 표현될 수 있을 거라는 느낌을 풍긴다.

이 문제의 어려움은 $n+1$개의 직사각형 중 $n$개는 정확히 계단 모서리에 하나씩 걸치지만 딱 한 개의 직사각형은 중앙 어디에든 위치할 수 있다는 점에 있다.

 

따라서 중앙 어디에든 위치할 수 있는 직사각형의 위치를 고정시킨다면 문제가 수월해질 것이다.

 

고정했다고 생각하고 문제를 바라보면, 직사각형의 두 변을 연장해서 가능한 답의 꼴들을 찾아볼 수 있다.
무조건 두 변 중에 한 변의 연장선은 어떤 조각도 가로지르지 않는다는 관찰이 핵심적이다.

 

이를 이용하여 약간의 포함배제를 적용하면 문제를 해결할 수 있다.

 

 

#include <bits/stdc++.h>
#define rep(i,a,b) for (ll i = (a); i <= (b); ++i)
using namespace std; using ll = long long;

const ll N = 103;
ll n, M;
ll C[N], D[N];

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> M;
    D[0] = D[1] = 1;
    rep(i,2,n) {
        rep(j,0,i-1) {
            D[i] += D[j]*D[i-j-1]%M;
            D[i] %= M;
        }
    }
    rep(i,1,n) {
        rep(x,1,i) rep(y,1,i-x) {
            // 1<=x,y && x+y<=i
            C[i] += D[x]*D[i-x]%M;
            C[i] += D[y]*D[i-y]%M;
            C[i] -= D[x]*D[y]%M*D[i-x-y]%M;
            C[i] %= M;
        }
        if (C[i]<0) C[i] += M;
    }

    rep(i,1,n) {
        ll ans=0;
        rep(x,0,i) rep(y,0,i-x) {
            // 0<=x,y && x+y<=i
            ans += D[x+y]*C[i-x-y]%M;
            ans %= M;
        }
        if (ans<0) ans += M;
        cout << ans << ' ';
    }
}