本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
给定一个非负整数数组 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 <= 12
0 <= A[i] <= 1e9
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-squareful-arrays
class Solution:
def numSquarefulPerms(self, A: List[int]) -> int:
# if len(A)==1:return 0
def is_square(i):
return i == math.isqrt(i) ** 2
# def ok(a):
# for i in range(len(a)-1):
# if not is_square(a[i]+a[i+1]):
# return False
# return True
# res=[]
# for p in itertools.permutations(A):
# if ok(p):
# res.append(p)
# return len(set(res))
n=len(A)
cnt=collections.Counter(A)
graph={x:[] for x in cnt}
for x in cnt:
for y in graph:
if is_square(x+y):
graph[x].append(y)
def dfs(x,do):
cnt[x]-=1
if do==0:
res=1
else:
res=0
for y in graph[x]:
if cnt[y]:
res+=dfs(y,do-1)
cnt[x]+=1
return res
return sum(dfs(x,n-1) for x in cnt)
