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. 组合公式 ，我们已知 n!,1/(m!),1/(n-m)!,也就是inv[n]*fac[m]*fac[n-m]

4. a^(MOD-2)) 需要用到快速幂。快速幂简单的数就是折半幂的过程。比如 2^10,我们可以看成是(2^2)^5，然后遇到5，需要单独拆出一个，变成 (2^2)*(2^2)^4=(2^2)*((2^2)^2)^2,这样可以大大减少计算次数，乘法，加法，减法过程可以求余数，防止溢出

 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;
    }

5. DFS: 先排好一个子树，假设这个子树本身有 x1 个节点，有 y1 种排法，然后第二个子树的元素，实际上是插入前面元素的空格。比如原本有 x2个节点，则要把这x2个插入 x1+x2的空位之中，然后现在已有节点数目就变成 x1+x2，又当前子树有 y2种排法 y1*c(x1+x2,x2)*y2*c(x1+x2+x3,x3)*y3.....，算完所有子树后即可得到最终结果

class Solution {
        long[] fac;
        long[] inv;
    public int waysToBuildRooms(int[] prevRoom) {
        //1.建图
        Map> 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> 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;
    }
 
 
}