Link.

  给定数列 ({a_n})，求排列 ({p_n}) 的个数，使得 ((forall iin[1,n))(a_{p_i}a_{p_{i+1}} ot=k^2))，其中 (kinmathbb N)。

(mathcal{Solution})

  首先消掉每个数的平方因子，那么限制条件转化为 (a_{p_i} ot=a_{p_{i+1}})，我们可以把相等的数放在一个桶里。设桶的大小 (s_1,s_2,cdots,s_m)。

  若直接计数，难免需要考虑用过的 (a) 的信息。引入容斥，令 (f_i) 表示至少有 (i) 对数相邻数相等。则答案为：

  再用 DP 求 (f)，令 (g(i,j)) 表示把前 (i) 个桶分为 (j) 块，保证块内元素相同的方案数。转移考虑第 (i) 个桶的贡献：

  比较显然嘛，其中 (inom{s_m-1}{k-1}) 是隔板法划分第 (i) 个桶，(s_m!) 表示元素有序，(k!) 表示块无序。

  最后，找到 (f) 和 (g) 的关系：、

  可以发现 (g(m,k)) 实质上就是“至多有 (k-1) 个数不相邻”的方案数。

  暴力求这两个东西就好，复杂度 (mathcal O(n^3))。

(mathcal{Code})

#include <map>
#include <cstdio>

const int MAXN = 300, MOD = 1e9 + 7;
int n, fac[MAXN + 5], ifac[MAXN + 5], f[MAXN + 5], g[MAXN + 5][MAXN + 5];
std::map<int, int> num;

inline void addeq ( int& a, const int b ) { if ( ( a += b ) >= MOD ) a -= MOD; }

inline int qkpow ( int a, int b, const int p = MOD ) {
	int ret = 1;
	for ( ; b; a = 1ll * a * a % p, b >>= 1 ) ret = 1ll * ret * ( b & 1 ? a : 1 ) % p;
	return ret;
}

inline void init ( const int n ) {
	fac[0] = 1;
	for ( int i = 1; i <= n; ++ i ) fac[i] = 1ll * i * fac[i - 1] % MOD;
	ifac[n] = qkpow ( fac[n], MOD - 2 );
	for ( int i = n - 1; ~ i; -- i ) ifac[i] = ( i + 1ll ) * ifac[i + 1] % MOD;
}

inline int C ( const int n, const int m ) {
	return n < m ? 0 : 1ll * fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}

int main () {
	scanf ( "%d", &n ), init ( n );
	for ( int i = 1, a; i <= n; ++ i ) {
		scanf ( "%d", &a );
		for ( int j = 2; j * j <= a; ++ j ) for ( ; ! ( a % ( j * j ) ); a /= j * j );
		++ num[a];
	}
	int indx = 0, las = 0;
	g[0][0] = 1;
	for ( auto p: num ) {
		++ indx, las += p.second;
		for ( int j = 1; j <= las; ++ j ) {
			int& cur = g[indx][j];
			for ( int k = 1; k <= j && k <= p.second; ++ k ) {
				addeq ( cur, 1ll * g[indx - 1][j - k]
					* C ( p.second - 1, k - 1 ) % MOD * fac[p.second] % MOD * ifac[k] % MOD );
			}
		}
	}
	for ( int i = 1; i <= n; ++ i ) f[n - i] = 1ll * g[indx][i] * fac[i] % MOD;
	int ans = 0;
	for ( int i = 0; i < n; ++ i ) addeq ( ans, ( i & 1 ? MOD - 1ll : 1ll ) * f[i] % MOD );
	printf ( "%d
", ans );
	return 0;
}