不是很难的一题，但是我模数写成了 \(998244353\)。
首先，\(xy=a^2,yz=b^2 \implies xz=c^2\ (a,b,c\in \mathbb{Z})\)。也就是说有传递性。
所以，rephrase the problem：
有 \(N\) 个球，每个球有一个颜色，问有多少排列，满足没有同种颜色的球相邻？
先把颜色排序。
设 \(dp_{i,j,k}\) 表示考虑到 \(i\)，有 \(j\) 个和 \(i\) 颜色不同的相同相邻的球，有 \(j\) 个和 \(i\) 颜色相同的相同相邻的球。
分类讨论即可。
-
\(col_i\neq col_{i-1}\)
- \(i\) 在不同颜色球之间：
\(dp_{i,j,0}+=dp_{i-1,j-k,k}\times{(i-j)}\) - \(i\) 在相同颜色球之间：
\(dp_{i,j,0}+=dp_{i-1,j-k+1,k}\times (j+1)\)
- \(i\) 在不同颜色球之间：
-
\(col_i= col_{i-1}\)，令 \(cnt\) 为已经出现了多少个 \(i\) 颜色（不包含 \(i\)）
- \(i\) 在与 \(i\) 相同球旁边：
\(dp_{i,j,k}+=dp_{i-1,j,k-1}\times (2\times cnt-k+1)\) - \(i\) 在与 \(i\) 不同球中间，两边求相同：
\(dp_{i,j,k}+=dp_{i-1,j+1,k}\times (j+1)\) - \(i\) 在与 \(i\) 不同球中间，两边求不同：
\(dp_{i,j,k}+=dp_{i-1,j,k}\times (i-2\times cnt+k-j)\)
- \(i\) 在与 \(i\) 相同球旁边：