python - 无序逃逸——Google Foobar 2020 未通过测试用例

问题描述

代码运行良好，并在 python 编译器中在线执行，但在 Google Foobar 中的所有测试用例均失败

from math import factorial
from collections import Counter
from fractions import gcd

def cycle_count(c, n):
    cc=factorial(n)
    for a, b in Counter(c).items():
        cc//=(a**b)*factorial(b)
    return cc        

def cycle_partitions(n, i=1):
    yield [n]
    for i in range(i, n//2+1):
        for p in cycle_partitions(n-i, i):
            yield [i]+p

def solution(w, h, s):    
    grid=0
    for cpw in cycle_partitions(w):
        for cph in cycle_partitions(h):            
            m=cycle_count(cpw, w)*cycle_count(cph, h)
            grid+=m*(s**sum([sum([gcd(i, j) for i in cpw]) for j in cph]))
    return grid//(factorial(w)*factorial(h))

查看要执行的代码。希望得到建议！

标签： pythonpython-3.xpython-2.7data-structures

从数学和算法的角度来看，这是一个非常棒的问题。

让我试着解释每个部分。

数学

这部分最好用排版好的公式来阅读。请参阅此处的简明解释，其中提供了进一步阅读的链接。

让我在这里直接添加一个参考：例如 Harary 和 Palmer 的图形枚举，第 2 章。

简而言之，有一个集合（整个矩阵集h x w，其中的条目可以采用任何s不同的值）和一组置换，它们可以将一些矩阵转换为其他矩阵。在该问题中，该组由矩阵的行和/或列的所有排列组成。

矩阵集被划分为可以相互转换的矩阵类。问题的目标是计算这些类的数量。在技术术语中，类的集合被称为群的作用或轨道空间的商。

好消息是有一个强大的定理（有许多概括和版本）可以做到这一点。这就是波利亚的枚举定理。该定理表示轨道空间元素的数量，用该区域中称为循环指数的多项式的值表示。现在，在这个问题中，群是两个特殊群的直接乘积，这两个群分别是和元素的所有排列的群。这些组的循环索引多项式是已知的，用于根据因子的循环索引多项式计算组乘积的循环索引多项式的公式也是已知的。hw

也许一个值得提出来激发多项式名称的评论如下：元素的每个排列都可以看作是这些元素的循环不相交子集。例如，(1,2,3,4,5)的排列可以是(2,3,1,5,4)，这里我们的意思是2移到1的位置，3移到1的位置2, 1 到 3 的位置， 5 到 4 的位置， 4 到 5 的位置。这种排列的效果与循环 1-> 3 -> 2 和 2 回到 1，循环 4 - > 5 和 5 返回 4。类似于如何将自然数分解为素数的乘积，每个排列都可以分解为不相交的循环。对于每个排列，循环在某种意义上对于每个排列都是唯一的。循环索引多项式是根据组中每个排列的每个长度的循环数来计算的。

将所有这些放在一起，我们得到总计数由链接中的最后一个公式给出。

执行

如最终公式所示，我们需要计算：

对于这些，我们可以这样做：

要计算所有分区，可以使用这里的迭代算法。已经在这里用 Python 编写。
一种有效的计算方法gcd可以使用欧几里得算法。但是，由于我们将需要一个范围内所有数字对的 gcd 并且每个数字对多次。最好通过动态编程一次性预先计算gcd的全表。如果a>b，那么gcd(a,b)=gcd(a-b,b)。该递归方程允许根据较小对的 gcd 计算较大对的 gcd。在表中，一个具有初始值gcd(1,a)=gcd(a,1)=1和gcd(a,a)=a，对于所有a。
阶乘也是如此。该公式将要求每个范围内所有数字的阶乘多次。n! = n(n-1)!因此，最好使用和从下往上计算它们0!=1!=1。

Python 中的实现可能如下所示。随意改进它。

python - 无序逃逸——Google Foobar 2020 未通过测试用例

问题描述

解决方案

推荐阅读