we derive a new(?) formula
def find_amountofsquareroots(perm: Permutation):
def member_of_sum(n, cyclen, k):
return (math.factorial(n) * cyclen ** k) // (math.factorial(k) * (2 ** k) * math.factorial(n - 2 * k))
def odd_count(n, cyclen):
total_sum = 0
for k in range(0, n // 2 + 1):
total_sum += member_of_sum(n, cyclen, k)
return total_sum
def even_count(n, cyclen):
assert n % 2 == 0, 'для извлечения корня m должно быть четным'
return member_of_sum(n, cyclen, n // 2)
psp = perm.passport()
answer = 1
for cycle_len, cnt in psp.items():
if cycle_len % 2 != 0:
answer *= odd_count(cnt, cycle_len)
else:
if cnt % 2 == 0:
answer *= even_count(cnt, cycle_len)
else:
answer = 0
break
return answer
I repeat that I could be wrong, since I could not check my formula in the available sources of information.