BOJ 28294 - 프랙탈

BOJ 28294 - 프랙탈

각 단계마다 그 다음단계에서 비워지는 지워지는 부분을 제거하고 생각해보자.

처음에 길이는 $n^a$ 개가 $n$개 있으므로 $n \cdot n^a$ 지만 그 다음 단계에서 $n^{a-1}$ 이 한 변마다 없어지므로

$n \cdot (n^a-n^{a-1})$ 이 더해진다고 생각할 수 있다.

그 다음 단계는 $n(n-1)$ 개의 변이 생기는데 똑같이 $(n^{a-1}-n^{a-2})$ 가 곱해져서

$n(n-1)(n^{a-1}-n^{a-2})$ 이다.

똑같이 그 다음단계는 $n(n-1)^2(n^{a-2}-n^{a-3})$ 이다.

근데 이 식을 잘 정리하면

$$ \begin{aligned} n^a(n-1) \\ n^{a-1}(n-1)^2 \\ n^{a-2}(n-1)^3 \\ \vdots \end{aligned} $$

이여서 결국 등비수열의 합공시인 $s=\dfrac{a_1\left( 1-r^n \right)}{1-r}$ 이므로 $a_1=n^a(n-1)$ 이고 $r=\dfrac{n-1}{n}$ 인것으로 생각하면

식을 잘 정리해서 분할정복을 이용한 거듭제곱을 쓰면 된다.

그런데 마지막 항은 $n^{a-a}-n^{a-(a+1)}$ 이 될 수 없으므로 $n^0$ 만 사용해주는 방식으로 다시 $n \cdot (n-1)^a$ 를 더해주는 방식으로 답을 구해주자.

const ll mod = 1e9 + 7;  
inline ll md(ll x) { return md(mod, x); }  
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() {  
   int n, a;  
   cin >> n >> a;  
   int ans = md(poww(n, a + 1) * (n - 1));  
   ans = md(ans - n * poww(n - 1, a + 1));  
   ans = md(ans + n * poww(n - 1, a));  
   cout << ans;  
}