title
给定一个非负整数数组 A，如果该数组每对相邻元素之和是一个完全平方数，则称这一数组为正方形数组。
返回 A 的正方形排列的数目。两个排列 A1 和 A2 不同的充要条件是存在某个索引 i，使得 A1[i] != A2[i]。
示例 1：
输入：[1,17,8]
输出：2
解释：
[1,8,17] 和 [17,8,1] 都是有效的排列。
示例 2：
输入：[2,2,2]
输出：1
提示：
1 <= A.length <= 120 <= A[i] <= 1e9
solution
class Solution:
def numSquarefulPerms(self, nums: List[int]) -> int:
n = len(nums)
can = [[False] * n for _ in range(n)]
import math
for i in range(n):
for j in range(i + 1, n):
v = nums[i] + nums[j]
k = math.sqrt(v)
if int(k) == k:
can[i][j] = True
can[j][i] = True
dp = [[0] * n for _ in range(1 << n)]
for mask in range(1 << n):
for i in range(n):
if (1 << i) & mask:
bit = mask ^ (1 << i)
if bit == 0:
dp[mask][i] = 1
continue
for j in range(n):
if (1 << j) & bit and j != i and can[i][j]:
dp[mask][i] += dp[bit][j]
ans = sum(dp[(1 << n) - 1])
div = 1
counter = collections.Counter(nums)
for k, v in counter.items():
if v > 1:
div *= math.prod(range(1, v + 1))
return ans // div