1

有N种颜色的珠子。你有第 i 个颜色的双珠。您想通过将所有珠子连​​接在一起来制作装饰品。您可以使用以下算法创建装饰品：

步骤#1 以任何顺序排列所有珠子，使相同颜色的珠子放在一起。

步骤#2 装饰品最初仅由排列中的第一个珠子组成。

步骤#3 对于每个后续的珠子，将其连接到装饰品中相同颜色的珠子上。如果没有相同颜色的珠子，它可以连接到装饰品中的任何珠子上。

所有珠子都是不同的，即使它们具有相同的颜色。按照上面的算法可以形成多少种不同的饰品？如果两个珠子在一种配置中通过线连接，但在另一种配置中不连接，则认为两种装饰品不同。

澄清

把珠子的形成想象成一棵树，而不是一条直线。任何数量的珠子都可以连接到一个珠子上。

这个问题快把我逼疯了！我听说你必须使用 Cayleys 算法来获得为每个颜色 ci 的珠子构建一棵树的所有方法，然后你必须将这些树连接在一起。据说有这个公式将组件连接到树中，(s1s2...sk) × nk - 2，但我不确定我的公式是否正确，也不相信。有没有人熟悉这个公式，或者可以帮助我解决这个问题。多谢你们。哦，顺便说一句，这是我到目前为止的算法。它正在处理一些测试用例，但也失败了。

公共类珠饰{

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

}

4

2 回答 2

2

使用指数函数和大量乘法时要注意的一件事是溢出。如果超过 2 52 ，双打就会失去精度。16 个珠子已经超过了这个限制。

考虑改用Java BigInteger。凯莱公式则变为：

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;
}
于 2013-06-04T18:55:05.990 回答
0

这是最终的答案。非常感谢 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);
    }
}
于 2013-06-04T21:02:28.177 回答