백준 31002 - 그래프 변환

https://www.acmicpc.net/problem/31002

 

문제에 주어진 변환을 직접 손으로 해보자. 그러면 다음 사실을 발견할 수 있다.

 

차수를 $deg$이라고 할 때, 첫 변환에서 정점이 될 간선에서 연결된 기존 $G$의 정점으로 하여금 각각 연결된 간선이 $deg - 1$개만큼 존재하여 총 $2(deg - 1)$ 만큼의 간선이 새로 생기고 역시 새로운 차수가 된다.

 

이때 총 간선의 개수는 악수 정리에 의해 $\frac {VE}{2}$가 된다.

 

간선이 어떻게 증가하는지 파악했으니 위 계산을 $K$번 반복해주면 답을 구할 수 있다.

 

정답 코드

#pragma GCC target("avx,avx2,fma,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
 
using namespace std;
using namespace __gnu_pbds;
 
using pii = pair<int, int>;
using ll = int_fast64_t;
 
int n, k;
 
constexpr ll mod = 1e9+7;
constexpr ll modinv = 500000004;
 
void solve()
{
  cin >> n >> k;
 
  ll nodes = n;
  ll degree = n - 1;
  ll edges = n * (n - 1) % mod * modinv % mod;
  
  for (int i = 0; i < k; i++)
  {
    ll next_nodes = edges;
    degree = (degree - 1) * 2 % mod;
    edges = degree * next_nodes % mod * modinv % mod;
 
    nodes = next_nodes;
  }
 
  cout << nodes;
}
 
int main()
{
#ifdef LOCAL
//  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
 
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}