<p>This is a gorgeous problem, both mathematically and from the algorithmic point of view.</p>
<p>Let me try to explain each part.</p>
<p><strong>The mathematics</strong></p>
<p>This part is better read with nicely typeset formulas. See a concise explanation <a href="https://franklinvp.github.io/2020-06-05-PolyaFooBar/" rel="noreferrer">here</a> where links to further reading are given.</p>
<blockquote>
<p>Let me add a reference directly here: For example Harary and Palmer's <em>Graphical enumeration</em>, Chapter 2.</p>
</blockquote>
<p>In short, there is a set (the whole set of <code>h x w</code>-matrices, where the entries can take any of <code>s</code> different values) and a <a href="https://en.wikipedia.org/wiki/Permutation_group" rel="noreferrer">group of permutations</a> that transforms some matrices in others. In the problem the group consists of all permutations of rows and/or columns of the matrices.</p>
<p>The set of matrices gets divided into classes of matrices that can be transformed into one another. The goal of the problem is to count the number of these classes. In technical terminology the set of classes is called the <em>quotient of the set by the action of the group</em>, or <em>orbit space</em>.</p>
<p>The good thing is that there is a powerful theorem (with many generalizations and versions) that does exactly that. That is <a href="https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem" rel="noreferrer">Polya's enumeration theorem</a>. The theorem expresses the number of elements of the orbit space in terms of the value of a polynomial known in the area as <em>Cycle Index</em>. Now, in this problem the group is a <a href="https://en.wikipedia.org/wiki/Direct_product_of_groups#:%7E:text=In%20mathematics%2C%20specifically%20in%20group,of%20direct%20product%20in%20mathematics." rel="noreferrer">direct product</a> of two special groups <a href="https://en.wikipedia.org/wiki/Symmetric_group" rel="noreferrer">the group of all permutations</a> of <code>h</code> and <code>w</code> elements, respectively. The Cycle Index polynomials for these groups are known, and so are formulas for computing the Cycle Index polynomial of the product of groups in terms of the Cycle Index polynomials of the factors.</p>
<p>Maybe a comment worth making that motivates the name of the polynomial is the following:
Every permutation of elements can be seen as cycling disjoint subsets of those elements. For example, a permutation of (1,2,3,4,5) and can be (2,3,1,5,4), where we mean that 2 moved to the position of 1, 3 moved to the position of 2, 1 to the position of 3, 5 to the position of 4 and 4 to the position of 5. The effect of this permutation is the same as cycling 1-&gt; 3 -&gt; 2 and 2 back to 1, and cycling 4 -&gt; 5 and 5 back to 4. Similar to how natural numbers can be factored into a product of prime factors, each permutation can be factored into disjoint cycles. For each permutation, the cycles are unique in a sense for each permutation. The Cycle Index polynomial is computed in terms of the number of cycles of each length for each permutation in the group.</p>
<p>Putting all these together we get that the total count is given by the last formula in the link.</p>
<p><strong>Implementation</strong></p>
<p>As seen in the final formula, we need to compute:</p>
<ol>
<li><a href="https://en.wikipedia.org/wiki/Partition_(number_theory)" rel="noreferrer">Partitions of a number</a></li>
<li><a href="https://en.wikipedia.org/wiki/Greatest_common_divisor#:%7E:text=In%20mathematics%2C%20the%20greatest%20common,8%20and%2012%20is%204." rel="noreferrer">Greatest common divisors</a> (gcd) of many numbers.</li>
<li><a href="https://en.wikipedia.org/wiki/Factorial" rel="noreferrer">Factorials</a> of many numbers.</li>
</ol>
<p>For these, we can do:</p>
<ol>
<li>To compute all partitions one can use the iterative algorithms <a href="https://arxiv.org/pdf/0909.2331.pdf" rel="noreferrer">here</a>. Already written in Python <a href="https://jeromekelleher.net/generating-integer-partitions.html" rel="noreferrer">here</a>.</li>
<li>An efficient way to compute <code>gcd</code> one could use <a href="https://en.wikipedia.org/wiki/Euclidean_algorithm#:%7E:text=In%20mathematics%2C%20the%20Euclidean%20algorithm,them%20both%20without%20a%20remainder." rel="noreferrer">Euclidean algorithm</a>. However, since we are going to need the gcd of all pairs of numbers in a range and each one many times. It is better to pre-compute the full table of gcd all at once by <em>dynamic programming</em>. If <code>a&gt;b</code>, then <code>gcd(a,b)=gcd(a-b,b)</code>. This recurrence equation allows to compute gcd of larger pairs in terms of that of smaller pairs. In the table, one has the initial values <code>gcd(1,a)=gcd(a,1)=1</code> and <code>gcd(a,a)=a</code>, for all <code>a</code>.</li>
<li>The same happens for factorials. The formula will require the factorials of all numbers in a range many times each. So, it is better to compute them all from the bottom up using that <code>n! = n(n-1)!</code> and <code>0!=1!=1</code>.</li>
</ol>
<p>An implementation in Python could look like <a href="https://github.com/franklinvp/foobar/blob/master/foobar2020/solutionProblem1.py" rel="noreferrer">this</a>. Feel free to improve it.</p>
Disorderly escape-Google Foobar 2020 not passing test cases
<p>The code is running fine and is executing in python compiler online but failing all test cases in the Google Foobar </p>

<pre><code>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))
</code></pre>

<p>Check out this code which is to be executed .Would love suggestions !!!</p>