從dif構建ornamet的方法彩珠（圖論算法）

Question

有N種顏色的珠子。你有第ith顏色的雙珠。你想通過連接所有的珠子來製作裝飾品。您可以使用以下算法創建裝飾：

步驟＃1以任意順序排列所有珠子，使相同顏色的珠子放在一起。

步驟＃2飾品最初只包含排列中的第一個珠子。

步驟＃3對於每個後續的珠子順序，將其加入裝飾中相同顏色的珠子。如果沒有相同顏色的珠子，它可以連接到裝飾中的任何珠子上。

所有的珠子都是不同的，即使它們具有相同的顏色。遵循上述算法可以形成多少種不同的裝飾物？如果兩個珠子在一個配置中由一個線連接，而另一個配置中沒有連接，則認爲兩個飾物是不同的。

澄清

把珠子形成想象成一棵樹，而不是一條直線。任何數量的珠子都可以連接到珠子上。

這個問題讓我瘋狂！我被告知你必須使用Cayleys算法來獲取所有的方法來爲每個顏色ci的珠子構建一棵樹，然後你必須將樹結合在一起。假設有一個將組件加入樹中的公式（s1s2。。sk）×nk - 2，但我不確定我是否擁有公式，也不相信。是否有人熟悉這個公式，或者可以幫助我解決這個問題。多謝你們。哦，順便說一句，這是我迄今爲止的算法。它正在處理一些測試案例，但也失敗了。

公共類BeadOrnament {

public static void main(String[] args) { 

    Scanner stdin = new Scanner(System.in); 

    int T, N; 

    T = stdin.nextInt(); 

    while (T-- > 0) { 

     N = stdin.nextInt(); 

     double[] colors = new double[N]; 
     double[] trees = new double[N]; 

     long ornaments = 0; 

     for (int i = 0; i < N; i++) { 
      colors[i] = stdin.nextInt(); 
     } 

     long t = 1; 
     for (int i = 0; i < N; i++) { 
      trees[i] = Math.max(Math.pow(colors[i], colors[i] - 2), 1); 
      t *= trees[i]; 
     } 

     long s = 1; 

     if (N > 1) { 

      for (int i = 0; i < N; i++) { 
       s *= colors[i]; 
      } 

      s *= Math.max(Math.pow(N, colors.length - 2), 1); 

     } 

     ornaments = s * t; 

     System.out.println(ornaments); 
    } 
} 

}

Answer 1

有一件事要小心使用指數函數和大量的乘法溢出時的感覺。如果你超過2 ，雙打失去精確度。這個限制已經超過了16個珠子。

請考慮使用Java的BigInteger代替。 Cayleys公式然後變成：

BigInteger numberOfOrnaments(int beadCount) { 
    if (beadCount <= 2) { 
     return BigInteger.ONE; 
    } 
    return BigInteger.valueOf(beadCount).pow(beadCount-2); 
} 

我找不到任何加入裝飾物（生成樹）在一起的公式。您的代碼至少應該對N <= 2正確，因爲您只添加一個字符串。對於N > 2我不能說它會不會起作用。

我的直覺是，你可以通過將任意兩個珠子（每棵樹中的一個）連接在一起來連接兩棵樹。對於珠粒計數n1和n2，這可以通過n1*n2的方式完成。第三棵樹可以連接到其他兩棵樹中的任何一棵，但也可以將它們連接到第三棵樹，而不必先加入它們。該公式很快變得非常複雜。

---

啊。現在我明白了。我想到的複雜配方，加入裝飾品，簡化到n1*n2*n3*...*nk*(n1+n2+n3+...+nk)^(k-2)，其中每個ni是顏色i的珠數。

BigInteger totalNumberOfConfigurations(int[] beadCounts) { 
    BigInteger result = BigInteger.ONE; 
    int sum = 0; 
    for (int n : beadCounts) { 
     result = result.multiply(numberOfOrnaments(n)) 
     result = result.multiply(BigInteger.valueOf(n)); 
     sum += n; 
    } 
    BigInteger x = BigInteger.valueOf(sum).pow(beadCounts.length - 2); 
    result = result.multiply(x); 
    return result; 
} 

Answer 2

下面是最終答案。非常感謝Markus Jarderot。就在你的文章之前，我已經嘗試了你給出的正確公式，但是我的實現有一個錯誤，錯誤的變量使用（愚蠢的錯誤）。再次感謝。

import java.math.BigInteger; 
import java.util.Scanner; 

public class BeadOrnament { 

    public static void main(String[] args) { 
     // TODO code application logic here 
     Scanner stdin = new Scanner(System.in); 

     int T, N; 

     T = stdin.nextInt(); 

     while (T-- > 0) { 

      N = stdin.nextInt(); 

      int[] colors = new int[N]; 
      BigInteger[] trees = new BigInteger[N]; 

      BigInteger ornaments; 

      for (int i = 0; i < N; i++) { 
       colors[i] = stdin.nextInt(); 
      } 

      BigInteger t = BigInteger.valueOf(1); 
      for (int i = 0; i < N; i++) { 
       trees[i] = numberOfTrees(colors[i]); 
       t = t.multiply(trees[i]); 
      } 

      BigInteger sp = BigInteger.valueOf(1); 
      BigInteger ss = BigInteger.valueOf(0); 
      BigInteger tot = BigInteger.valueOf(0); 

      for (int i = 0; i < N; i++) { 
       sp = sp.multiply(BigInteger.valueOf(colors[i])); 
       ss = ss.add(BigInteger.valueOf(colors[i])); 
      } 

      if (N > 2) { 
       ss = ss.pow(colors.length - 2); 
       ss = ss.multiply(sp); 
       tot = ss; 
       ornaments = tot.multiply(t); 
      } else if (N == 2) { 
       tot = sp; 
       ornaments = tot.multiply(t); 
      } else { 
       ornaments = t; 
      } 

      System.out.println(ornaments.mod(BigInteger.valueOf(1000000007))); 
     } 
    } 

    public static BigInteger numberOfTrees(int beadCount) { 
     if (beadCount <= 2) { 
      return BigInteger.ONE; 
     } 
     return BigInteger.valueOf(beadCount).pow(beadCount - 2); 
    } 
}