该代码运行良好并且正在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))
签出将要执行的代码。有爱的建议！！！
从数学上和从算法的角度来看，这都是一个巨大的问题。
让我尝试解释每个部分。
数学
使用良好的排版公式可以更好地阅读此部分。请在此处查看简明解释，其中提供了指向进一步阅读的链接。
让我在这里直接添加参考：例如Harary和Palmer的图形枚举，第2章。
简而言之，有一组（整个h x w-matrices，其中的条目可以采用任何s不同的值）和一组置换，这些置换将一些矩阵转换为其他矩阵。在问题中，该组由矩阵的行和/或列的所有排列组成。
一组矩阵被划分为几类可以相互转换的矩阵。问题的目的是计算这些类的数量。在技术术语中，类的集合称为该集合与组或轨道空间的作用的商。
好消息是，有一个强大的定理（具有许多归纳和版本）可以做到这一点。这就是Polya的枚举定理。该定理用该区域称为循环指数的多项式的值表示轨道空间的元素数。现在，在这个问题中，组是两个特殊组的直接乘积，这两个特殊组分别是和的所有排列的组。这些组的循环指数多项式是已知的，并且根据因子的循环指数多项式来计算组乘积的循环指数多项式的公式也是已知的。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。类似于可以将自然数分解为素数乘积的方法，每个排列也可以分解为不相交的循环。对于每个排列，循环在某种意义上对于每个排列都是唯一的。根据组中每个排列的每个长度的循环数来计算循环指数多项式。
将所有这些放在一起，我们得到的总数是由链接中的最后一个公式给出的。
实作
如最终公式所示，我们需要计算：
为此，我们可以这样做：
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)!and从头开始进行计算0!=1!=1。Python中的实现可能看起来像这样。随时进行改进。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句