1916. 統計為蟻群構築房間的不同順序 費馬小定理+快速幂+DFS

1916. 統計為蟻群構築房間的不同順序

你是一隻螞蟻，負責為蟻群構築 ​

​n​

​​ 間編号從 ​

​0​

​​ 到 ​

​n-1​

​ 的新房間。給你一個 下标從 0 開始 且長度為 ​

​n​

​​ 的整數數組 ​

​prevRoom​

​​ 作為擴建計劃。其中，​

​prevRoom[i]​

​​ 表示在構築房間 ​

​i​

​​ 之前，你必須先構築房間 ​

​prevRoom[i]​

​ ，并且這兩個房間必須 直接 相連。房間 ​

​0​

​​ 已經構築完成，是以 ​

​prevRoom[0] = -1​

​​ 。擴建計劃中還有一條硬性要求，在完成所有房間的構築之後，從房間 ​

​0​

​ 可以通路到每個房間。

你一次隻能構築 一個 房間。你可以在 已經構築好的 房間之間自由穿行，隻要這些房間是 相連的 。如果房間 ​

​prevRoom[i]​

​​ 已經構築完成，那麼你就可以構築房間 ​

​i​

​。

傳回你構築所有房間的 不同順序的數目 。由于答案可能很大，請傳回對 ​

​109 + 7​

​ 取餘 的結果。

示例 1：

輸入：​

​prevRoom​

​ = [-1,0,1]

輸出：1

解釋：僅有一種方案可以完成所有房間的構築：0 → 1 → 2

示例 2：

輸入：​

​prevRoom​

​ = [-1,0,0,1,2]

輸出：6

解釋：

有 6 種不同順序：

0 → 1 → 3 → 2 → 4

0 → 2 → 4 → 1 → 3

0 → 1 → 2 → 3 → 4

0 → 1 → 2 → 4 → 3

0 → 2 → 1 → 3 → 4

0 → 2 → 1 → 4 → 3

提示：

• ​

  ​n == prevRoom.length​

  ​
• ​

  ​2 <= n <= 105​

  ​
• ​

  ​prevRoom[0] == -1​

  ​
• 對于所有的​

  ​1 <= i < n​

  ​​ ，都有​

  ​0 <= prevRoom[i] < n​

  ​
• 題目保證所有房間都構築完成後，從房間​

  ​0​

  ​ 可以通路到每個房間

來源：力扣（LeetCode）

連結：https://leetcode.cn/problems/longest-univalue-path

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

做題結果

失敗，方法完全對，但是不掌握組合數用的費馬小定理，就搞不定。1e5的話，不可以用楊輝三角算。上次偷懶沒學，這次也不算完全懂，但是會用了

方法：快速幂+費馬小定理+DFS

1. 費馬小定理用在組合數怎麼用（因為找了很多資料，還是看不懂，最後大概通過結論猜出怎麼用），單從組合數而言，(1/a)%MOD當做 (a^(MOD-2)) 處理

2. 階乘：x! 這個簡單吧，循環連乘即可，用 inv[i]表示。1/(k!) 可以用費馬小定理搞定 用fac[i]表示

3. 組合公式 

private long pow(long a, long b){
        long ans = 1L;
        while (b>0){
            if((b&1)==1){
                ans = ans*a%MOD;
            }
            b=b/2;
            a= a*a%MOD;
        }
        return ans;
    }      

class Solution {
        long[] fac;
        long[] inv;
    public int waysToBuildRooms(int[] prevRoom) {
        //1.建圖
        Map<Integer,Set<Integer>> graph = new HashMap<>();
        int n = prevRoom.length;
        for(int i = 1;i < n; i++){
            graph.computeIfAbsent(prevRoom[i],o->new HashSet<>()).add(i);
        }

        fac = new long[n];
        inv = new long[n];
        fac[0]=inv[0]=1;
        for(int i = 1; i < n; i++){
            fac[i] = fac[i-1]*i%MOD;
            inv[i] = pow(fac[i],MOD-2);
        }
        return (int) dfs(graph,-1,0)[0];
    }

    private long pow(long a, long b){
        long ans = 1L;
        while (b>0){
            if((b&1)==1){
                ans = ans*a%MOD;
            }
            b=b/2;
            a= a*a%MOD;
        }
        return ans;
    }


    long ans = 0L;
    final long MOD = (long) (1e9+7);
    //擺法+節點
    private long[] dfs(Map<Integer,Set<Integer>> graph, int pre, int index){
        if(!graph.containsKey(index) || (graph.size()==1&&graph.containsKey(pre))){
            return new long[]{1,1};
        }

        int total = 0;//總共選了幾個點
        long ans = 1L;
        for(int next:graph.get(index)){
            if(next==pre) continue;
            long[] item = dfs(graph,index,next);
            long c = getC((int)(total+item[1]),(int)item[1]);
            ans = ans * c%MOD*item[0]%MOD;
            total+=item[1];
        }

        return new long[]{ans,total+1};
    }

    private long getC(int a, int b){
        return fac[a]*inv[a-b]%MOD*inv[b]%MOD;
    }


}