AOJ - MORSE

AOJ - MORSE

같은 것이 있는 순열의 개수는 $\dfrac {(n+m)!}{n! \cdot m!}=\dbinom {n+m}n$ 이다. 이를 이용해서 $O(N^2)$에 일단 이항 계수 테이블을 만들어준다.

이후에 $K$ 번째 수를 찾는것은 $K-1$ 개의 수를 $skip$ 해야 한다는 것에 기반한다.

먼저 $K$ 를 1을 빼준다음에 그만큼 스킵을 시켜주는 것이다.

-를 앞에 붙일 수 있다는것은 -의 개수를 하나 빼고 만드는 조합의 개수가 $K$ 개보다 많아서 -를 붙이고도 진행을 할 수 있음을 의미한다.

현재 -와 o가 $x$개 $y$개로 모두 남아있을 때, -를 써서 $x-1$ 개의 -와 $y$ 개의 o를 써서 만들 수 있는 순열의 개수는 $\dbinom {x-1+y}y$ 개이고 이것이 현재 스킵해야될 개수인 $K$보다 많다면 그냥 -를 붙여준다.

그렇지 않다면 o를 붙여주고 -를 붙였을 때의 경우의 수인 저만큼 $K$에서 빼주면 된다.

int bino[222][222];  
void solve() {  
   int n, m, k;  
   cin >> n >> m >> k;  
   // 같은것이 있는 순열  
   // (n+m)! / (n! * m!)  
   for (int i = 0; i <= 222; i++)  
      for (int j = 0; j <= i; j++)  
         bino[i][j] = !i || !j ? 1 : min(bino[i - 1][j] + bino[i - 1][j - 1], int(1e9));  
  
   string ans;  
   function<void(int, int)> fn = [&](int i, int j) -> void {  
      if (i == 0 && j == 0) return;  
      if (!i) {  
         ans += 'o';  
         fn(i, j - 1);  
         return;  
      }  
      if (!j) {  
         ans += '-';  
         fn(i - 1, j);  
         return;  
      }  
  
      // i 를 썻을 때  
      int x = bino[i - 1 + j][j];  
      if (x > k) {  
         ans += '-';  
         fn(i - 1, j);  
      } else {  
         k -= x;  
         ans += 'o';  
         fn(i, j - 1);  
  
      }  
  
   };  
   k--;  
   fn(n, m);  
   cout << ans << endl;  
}