Pythonでn個のノードを持つすべての単純な無向グラフのコストの合計を見つけるプログラム

n個のノードを持つ無向グラフGがあるとします。ここで、単純な無向グラフのコストがそのノードのコストの合計であると考えてください。また、ノードのコストはD ^ kです。ここで、Dはその次数です。これで、n個とk個の値ができました。 n個のノードを持つすべての可能な単純な無向グラフのコストの合計を見つける必要があります。結果は非常に大きくなる可能性があるため、1005060097を法として結果を返します。

したがって、入力がn =3 k =2の場合、出力は36になります。これは、3つのノードを持つ8つの単純なグラフがあるためです。

• エッジが3つしかない1つのグラフで、コストは2 ^ 2 + 2 ^ 2 + 2 ^ 2=12です。
• 2つのエッジを持つグラフがあり、それぞれのコストは1 ^ 2 + 1 ^ 2 + 2 ^ 2=6です。
• 1つのエッジを持つ3つのグラフで、それぞれのコストは0 ^ 2 + 1 ^ 2 + 1 ^ 2=2です。
• エッジのない1つのグラフで、コストは0 ^ 2 + 0 ^ 2 + 0 ^ 2=0です。

したがって、合計は12 * 1 + 6 * 3 + 2 * 3 + 0 * 1=36です。

これを解決するには、次の手順に従います-

• 関数choose（）を定義します。これにはn、kがかかります
• product：=1
• nからn-kの範囲のiの場合、1ずつ減らします。
  • product：=product * i
• 1からkの範囲のiについては、
  • product：=product / i
• 製品を整数として返す
• 関数util（）を定義します。これにはd、nがかかります
• return Choose（n-1、d）* 2 ^（choose（n-1、2））
• メインの方法から、次の手順を実行します。
• 合計：=0
• 0からn-1の範囲のdの場合、do
  • total：=total + util（d、n）* d ^ k
  • total：=total mod 1005060097
• return（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))

入力

3, 2

出力

36