題目

男人八題 之 Connected Graph
題目內(nèi)容可以看上邊鏈接，這里不在贅述。就是求 n 個不同點的無向連通圖有多少種可能。

解題思路

我們假設(shè)，當(dāng)點為 n 個時：
a(n) 為無向連通圖的個數(shù)。
b(n) 為無向不連通圖的個數(shù)。
c(n) 為總個數(shù)。
很顯然，c(n) = a(n) + b(n);
其中 c(n) = $2^{(n(n-2)/2)}$ ，b(n) = $\sum_{i=1}^{n-1}C(n,i-1)a(i)*c(n-i)$
簡書貌似不支持?jǐn)?shù)學(xué)符號，那就是:

公式

證明

上邊給出的 c(n) 與 b(n) 的公式大家可能比較懵逼，我們來證明一下。

c(n)

1. 先求出 n 個不同點可以有多少種連線，就是 C(n,2)，C(n,2) = n*(n-1)/2，如果對這個有疑問的話，可以去看一下高數(shù)中排列組合部分。

2. 對于沒組連線，都有兩種狀態(tài)，一種是相連，一種是不相連，一共有 C(n,2) 組連線，所以總共的種類為 2^C(n,2)，即
   公式

b(n)

c(n) 是已知的，如果想求 a(n)，只要求出 b(n) 就可以了。
我們在 n 個點中隨意取一個點 A，A 的狀態(tài)一共有以下幾種：

1. A 與所有其他點都不連通。
2. A 只與其他點中的一個點連通。
3. A 只與其他點中的兩個點連通。
……
i. A 只與其他點中的 i - 1 個點聯(lián)通。
……
n-1. A 只與其他點中的 n-2 個點連通。

這就是所有的情況，那我們只要把每種狀態(tài)都計算出來然后相加，就是 b(n) 了，那接下來我們計算一下：

1. C(n,0)*a(1)*c(n-1)
2. C(n,1)*a(2)*c(n-2)
3. C(n,2)*a(3)*c(n-3)
……
i. C(n,i-1)*a(i)*c(n-i)
……
n-1. C(n,n-2)*a(n-1)*c(1)

代碼

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

public class Main {
    static BigInteger[] unConnected = new BigInteger[51];
    static BigInteger[] connected = new BigInteger[51];
    static BigInteger[] total = new BigInteger[51];

    // 為了方便，factorial[i] 為 i 的階乘
    static BigInteger[] factorial = new BigInteger[51];

    /**
     * 初始化階乘（避免重復(fù)運算）
     */
    private static void initFactorial() {
        factorial[0] = BigInteger.valueOf(1);
        factorial[1] = BigInteger.valueOf(1);
        for (int i = 2; i <= 50; i++) {
            factorial[i] = factorial[i - 1].multiply(BigInteger.valueOf(i));
        }
    }

    /**
     * 獲取排列組合結(jié)果
     */
    private static BigInteger getCombination(int total, int select) {
        if (select == 0) {
            return BigInteger.valueOf(1);
        }
        return factorial[total].divide(factorial[select].multiply(factorial[total - select]));
    }

    /**
     * 獲得不連通圖的數(shù)量，比如 10 個點的不連通圖數(shù)量， 這里 num 應(yīng)該為 10（而不是 9）
     */
    private static BigInteger getNnConnected(int num) {
        BigInteger sum = BigInteger.valueOf(0);
        for (int i = 1; i <= num - 1; i++) {
            sum = sum.add(getCombination(num - 1, i - 1).multiply(connected[i]).multiply(total[num - i]));
        }
        return sum;
    }

    public static void main(String[] args) {

        // 初始化階乘表
        initFactorial();

        unConnected[0] = BigInteger.valueOf(0);
        connected[0] = BigInteger.valueOf(0);
        total[0] = BigInteger.valueOf(0);

        // 計算總數(shù)、非連通圖數(shù)、連通圖數(shù)
        for (int i = 1; i <= 50; i++) {
            total[i] = BigInteger.valueOf(2).pow(i * (i - 1) / 2);
            unConnected[i] = getNnConnected(i);
            connected[i] = total[i].subtract(unConnected[i]);
        }

        // 輸入與輸出
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            if (n == 0) {
                return;
            }
            System.out.println(connected[n]);
        }
    }
}

你沒看錯，我慫了，實在不想用 C++ 再寫一遍大數(shù)運算，我用了 java......