algorithm - 珠饰算法

Question

一段时间以来，我一直在尝试理解这个问题。有人可以帮助理解这个问题吗？

============================================= ================================

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

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

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

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

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

更新/澄清

将珠子的形成想象成一棵树而不是一条直线。一个珠子可以连接任意数量的珠子。

输入:

第一行包含测试用例T的数量。后面是T个测试用例。每个测试用例在第一行包含 N - 珠子的颜色数。下一行包含N个整数，其中第i个整数bi表示第i种颜色的珠子数量。

输出:

输出 T 行，每个测试用例一行。所有答案都应以 1000000007 为模输出。

约束:

1 <= T <= 20

1 <= N <= 10

1 <= 双 <= 30

示例输入:

52个2 12个2 21个4个2个3 15个1 1 1 1 1示例输出:

24个169125说明:

对于第一种情况:让我们将珠子标记为 A1、A2 和 B1。最初，它们可以按 4 种方式排列 - “A1,A2,B1”、“A2,A1,B1”、“B1,A1,A2”和“B1,A2,A1”。

对于前两种排列方式中的每一种，装饰物可以以两种方式形成(第一种方式为 A1-A2-B1 或 B1-A1-A2，第二种方式为 A2-A1-B1 或 B1-A2-A1一个)。

对于最后两种排列中的每一种，装饰物都可以以一种方式形成。

然而，在总共 6 种可能的饰物中，只有 2 种独特的:A1 - A2 - B1 和 A2 - A1 - B1。

对于第二个测试用例:可能的唯一装饰品是 A1 - A2 - B1 - B2、A1 - A2 - B2 - B1、A2 - A1 - B1 - B2 和 A2 - A1 - B2 - B1。

对于第三个测试用例，可能更容易看出在 4 个顶点上只有两种类型的图:路径或星形。不难看出有12条路径和4颗星(解释礼貌:zlangley)

对于第五个测试用例，有很多人声称可能的方式总数是 5!/2 = 60 而答案是 125。一颗树。这意味着一种可能的安排是。将 A 视为根节点并具有两条边(A-B 和 A-C)。现在，将 B 视为具有两条边(B-D 和 B-E)的子根节点。这是一种可能的珠形成。

============================================= ==================================

PS:我得到这个问题的比赛现在已经结束，我只想了解这个问题。 ( https://www.hackerrank.com/challenges/beadornaments )

Answer 1

让我尝试重新表述这个问题:对给定的大质数求模，有多少无根树涉及 n 个成对不同的节点(珠)，受制于以下约束:对于给定分区(着色)的每个部分节点，由这些节点导出的子图是连通的(即，它是一棵树)？

这样的树由颜色内和颜色间的边组成。此外，前者的选择不会影响后者的有效选择集，反之亦然。对于每种颜色，颜色内边缘的选择又是独立的。对于具有 k 个节点的颜色，可能性的数量是 k^(k-2) by Cayley's formula .将它们相乘。

要确定颜色间边缘的可能性数量，请使用 Kirchhoff's matrix tree theorem计算一个图的生成树的数量，其中每个颜色是一个节点，并且在具有 k1 珠子的颜色和具有 k2 的另一种颜色之间有 k1*k2 条边，即具有珠子的完整图形中的生成树数每种颜色都收缩。由于答案是以大质数为模计算的，对于强多项式时间的算法，行列式计算可以通过例如高斯消去法来完成。