不是很难的一题,但是我模数写成了 \(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\) 相同球旁边: