BOJ 21739 - 펭귄 네비게이터

BOJ 21739 - 펭귄 네비게이터

Solution 1

놀랍게도(?) $O(4N^2)$ 로 그냥 DP 돌렸더니 뚫렸다.

void solve() {
   int n;
   cin >> n;
   for (int i = 2; i <= n * 2; i++) dp[1][i] = 1;
   for (int x = 2; x <= n; x++) {
      int I = x % 2, J = I ^ 1;
      for (int i = 1; i <= 2 * n; i++) {
         dp[J][i] += dp[J][i - 1];
         if (dp[J][i] >= mod) dp[J][i] %= mod;
      }
      for (int v = x * 2; v <= 2 * n; v++) {
         dp[I][v] += dp[J][v - 1];
         if (dp[I][v] >= mod) dp[I][v] %= mod;
      }
      fill(dp[J], dp[J] + 20005, 0);
   }
   cout << dp[n % 2][2 * n];
}

Solution 2

이 문제는 카탈란 수 문제이다.

일반항 $C(n)=\dfrac 1{n+1} \cdot \dbinom{2n}{n}=\dfrac {(2n)!}{(n+1)! \cdot n!}$ 를 써서 풀면 된다.

왜 카탈란수로 치환되는지는 공식 해설 을 참고하자.

const ll mod = 1e9 + 7;  
inline ll md(ll x) { return md(mod, x); }  
int dp[2][20005];  
array<ll, 3> gcdx(ll A, ll B) {  
   ll x1 = 1, x2 = 0, y1 = 0, y2 = 1, r1 = A, r2 = B;  
   while (r2) {  
      ll q = r1 / r2 - ((r1 ^ r2) < 0 && r1 % r2);  
      tie(x1, x2) = mp(x2, x1 - x2 * q);  
      tie(y1, y2) = mp(y2, y1 - y2 * q);  
      tie(r1, r2) = mp(r2, r1 - r2 * q);  
   }  
   return {x1, y1, r1};  
}  
void solve() {  
   int n;  
   cin >> n;  
   int t = 1, ans = 1;  
   for (int i = 1; i <= 2 * n; i++) {  
      t = md(t * i);  
      if (i == n) ans = md(ans * gcdx(t, mod)[0]);  
      if (i == n + 1) ans = md(ans * gcdx(t, mod)[0]);  
   }  
   ans = md(ans * t);  
   cout << ans;  
}