n개의 노드가 있는 무방향 그래프 G가 있다고 가정합니다. 이제 단순한 무방향 그래프의 비용이 노드 비용의 합이라고 생각해 보십시오. 노드의 비용은 D^k이며, 여기서 D는 해당 정도입니다. 이제 n 및 k 값이 있습니다. n개의 노드가 있는 모든 가능한 단순 무방향 그래프의 비용 합계를 찾아야 합니다. 결과가 매우 클 수 있으므로 resultmodulo 1005060097을 반환하십시오.
따라서 입력이 n =3 k =2와 같으면 출력은 36이 됩니다. 왜냐하면 3개의 노드가 있는 8개의 간단한 그래프가 있기 때문입니다.
- 간선이 3개인 그래프 1개, 비용은 2^2+2^2+2^2 =12입니다.
- 두 개의 간선이 있는 그래프가 있으며 각 간선의 비용은 1^2+1^2+2^2 =6입니다.
- 한 모서리가 있는 3개의 그래프, 각각의 비용은 0^2+1^2+1^2 =2입니다.
- 간선이 없는 하나의 그래프, 비용은 0^2+0^2+0^2 =0입니다.
따라서 합계는 12*1 + 6*3 + 2*3 + 0*1 =36입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- select() 함수를 정의합니다. n, k 가 걸립니다.
- 제품:=1
- n ~ n-k 범위의 i에 대해 1 감소, do
- 제품 :=제품 * i
- 1~k 범위의 i에 대해
- 제품 :=제품 / i
- 정수로 제품을 반환
- util() 함수를 정의합니다. d, n 이 걸립니다.
- select(n-1, d) * 2를 반환합니다 ^(choose(n-1, 2))
- 기본 방법에서 다음을 수행합니다.
- 총계:=0
- 0 ~ n - 1 범위의 d에 대해
- 총계 :=총계 + util(d, n) * d^k
- 총계 :=총 모드 1005060097
- 반환(총 * n) 모드 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))
입력
3, 2
출력
36