Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 노드가 n개인 모든 단순 무방향 그래프의 비용 합계 구하기

문제 이해하기

노드가 n개인 무방향 그래프 G가 있다고 가정해 보겠습니다. 단순 무방향 그래프의 비용(cost)은 그래프를 구성하는 모든 노드의 비용 합계로 정의되며, 각 노드의 비용은 Dk입니다. 여기서 D는 해당 노드의 차수(degree)이고, k는 주어진 지수입니다.

n과 k 값이 주어졌을 때, 노드가 n개인 모든 가능한 단순 무방향 그래프의 비용 총합을 구해야 합니다. 결과값이 매우 커질 수 있으므로 1005060097로 나눈 나머지를 반환합니다.

예제

입력이 n = 3, k = 2라고 해봅시다. 노드가 3개인 단순 그래프는 총 8개이며, 다음과 같이 분류할 수 있습니다.

  • 간선 3개: 그래프 1개, 비용은 2² + 2² + 2² = 12
  • 간선 2개: 그래프 3개, 각각의 비용은 1² + 1² + 2² = 6
  • 간선 1개: 그래프 3개, 각각의 비용은 0² + 1² + 1² = 2
  • 간선 0개: 그래프 1개, 비용은 0² + 0² + 0² = 0

따라서 전체 합계는 12×1 + 6×3 + 2×3 + 0×1 = 36입니다.

접근 방법

핵심 아이디어는 특정 노드 하나에 초점을 맞추는 것입니다. 어떤 노드 v의 차수가 정확히 d가 되도록 하는 그래프의 개수는 다음 두 부분으로 나누어 셀 수 있습니다.

  • 나머지 n−1개 노드 중에서 v와 연결할 이웃 d개를 고르는 경우의 수: C(n−1, d)
  • 나머지 n−1개 노드 사이의 간선은 자유롭게 넣거나 뺄 수 있습니다. 가능한 간선의 수는 C(n−1, 2)이므로, 조합은 총 2C(n−1, 2)가지입니다.

따라서 한 노드의 기여분은 C(n−1, d) × 2C(n−1, 2) × dk가 됩니다. 이 값을 d = 0부터 n−1까지 모두 더한 뒤, 노드가 총 n개이므로 전체에 n을 곱하면 원하는 답을 얻을 수 있습니다.

구현 단계를 정리하면 다음과 같습니다.

  1. 이항 계수를 계산하는 함수 choose(n, k)를 정의합니다.
  2. util(d, n) 함수는 choose(n−1, d) × 2^(choose(n−1, 2))를 반환합니다.
  3. d를 0부터 n−1까지 순회하며 total에 util(d, n) × dk를 누적하고, 매 단계마다 1005060097로 나머지를 취해 값이 불필요하게 커지지 않도록 합니다.
  4. 최종적으로 (total × n) mod 1005060097을 반환합니다.

구현 예제

아래 코드를 통해 동작 과정을 더 잘 이해할 수 있습니다.

def choose(n, k):
    product = 1
    for i in range(n, n-k, -1):
        product *= i
    for i in range(1, k+1):
        product //= i
    return int(product)

def util(d, n):
    return choose(n-1, d) * 2 ** (choose(n-1, 2))

def solve(n, k):
    total = 0
    for d in range(n):
        total += util(d, n) * d ** k
        total %= 1005060097
    return (total * n) % 1005060097

n = 3
k = 2
print(solve(n, k))

참고: 이항 계수를 계산할 때 실수 나눗셈(/) 대신 정수 나눗셈(//)을 사용하면 n이 커졌을 때 부동소수점 정밀도 손실을 피할 수 있습니다. 또한 n이 매우 큰 경우에는 2의 거듭제곱을 미리 계산하지 말고 pow(2, 지수, 1005060097)처럼 모듈러 거듭제곱을 활용하는 것이 효율적입니다.

입력

3, 2

출력

36