[Blog] [Docs] [Code] [Slides] [About]

BZOJ 1005 - 明明的烦恼

数学高精度

2020-03-26 16:37 CST

Problem

怎么又是组合数学,我吐了。

利用Prufer Code将树转换为序列求解:

  • 首先选出$sum$个位置填入指定的节点
  • 每个节点出现$a[i]-1$次,对这$sum$个位置求全排列数量
  • 剩下的$n-2-sum$个位置随意填入剩下的节点

答案即为

$${n-2 \choose sum} \times \dfrac{(sum)!}{\prod (a[i] - 1)!} \times (n-2-sum)^{n-cnt}$$

昨天不会写快速幂,今天连组合数都不会求了,危。

Solution

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

public class Main {
    static class Problem {
        int n, cnt, sum;
        int[] a;
        Problem(Scanner cin) {
            n = cin.nextInt();
            a = new int[n + 1];
            for (int i = 0; i < n; ++i) {
                a[i] = cin.nextInt();
                if (a[i] != -1) {
                    ++cnt;
                    sum += a[i] - 1;
                }
            }
        }
        public BigInteger solve() {
            if (sum > n - 2) return BigInteger.valueOf(0);

            BigInteger[] frac = new BigInteger[1005];
            frac[0] = frac[1] = BigInteger.valueOf(1);
            for (int i = 2; i <= 1000; ++i) {
                frac[i] = frac[i - 1].multiply(BigInteger.valueOf(i));
            }

            BigInteger ans = BigInteger.valueOf(1);
            // ans <- C(n - 2, sum)
            ans = ans.multiply(frac[n - 2]);
            ans = ans.divide(frac[sum]);
            ans = ans.divide(frac[n - 2 - sum]);
            // ans <- ans * (# of permutations of sum numbers of cnt groups)
            ans = ans.multiply(frac[sum]);
            for (int i = 0; i < n; ++i) {
                if (a[i] != -1) {
                    ans = ans.divide(frac[a[i] - 1]); // (a[i]-1)!
                }
            }
            // ans <- ans * (# of placement of rest n - cnt numbers int n-2 - sum places)
            ans = ans.multiply(BigInteger.valueOf(n - cnt).pow(n - 2 - sum));

            return ans;
        }
    }
    
    public static void main(String[] args) {
        Problem problem = new Problem(new Scanner(System.in));
        System.out.println(problem.solve());
    }
}
<EOF>