BOJ 13912 - 외계 생물

BOJ 13912 - 외계 생물

처음엔 총 $2^{H+1}-1$ 마리가 있다.

그럼이제 자식 두개에 $\dfrac{2^{H+1}-2}{2}$ 개 씩 분배해야한다.

이는 $\dbinom{2^{H+1}-2}{\dfrac{2^{H+1}-2}{2}}$ 이다.

저 개수대로 어떤 수들이 들어갔는지 중요해지지 않는다. 동일한 수만큼 나누면 어차피 거기서도 숫자들의 대소가 모두 정해지기 때문에 동일한 문제를 푸는 것이 된다.

따라서 DP + 조합론 문제이다.

그런데 단계마다 이항계수값을 $B$라고 하면 각 단계마다 $2$개씩 문제가 쪼개지기 때문에 $B$가 아닌 $B^{2^i}$ 만큼 정답에 곱해주야 한다.

const ll mod = 1e9 + 7;
inline ll md(ll x) { return md(mod, x); }
int pow2[12], bino[2500][2500];
inline ll poww(ll a, ll b) {
   ll ret = 1;
   while (b) {
      if (b & 1) {
         ret *= a;
         if (~mod) ret %= mod;
      }
      a *= a;
      if (~mod) a %= mod;
      b >>= 1;
   }
   return ret;
}
void solve() {
   for (int i = 0; i <= 2400; i++) {
      for (int j = 0; j <= i; j++) {
         bino[i][j] = !i || !j ? 1 : md(bino[i - 1][j] + bino[i - 1][j - 1]);
      }
   }
   debug(bino[6][2]);
   pow2[0] = 1;
   for (int i = 1; i <= 11; i++) pow2[i] = md(pow2[i - 1] * 2);
   int H;
   cin >> H;
   int ans = 1;
   for (int h = 1; h <= H; h++) {
      int len = pow2[H - h + 2] - 1;
      debug(h, len);
      int b = bino[len - 1][(len - 1) / 2];

      ans = md(ans * poww(b, pow2[h - 1]));
   }
   cout << ans;
}