840C

On the Bench 题面翻译 给定一个序列 \(a(a_i\le 10^9)\)，长度为 \(n(n\le 300)\)。 试求有多少 \(1\) 到 \(n\) 的排列 \(p_i\)，满足对于任意的 \(2\le i\le n\) 有 \(a_{p_{i-1}}\times a_{p_i} ......

一、题目描述： 给你一个长度为 $n$ 的序列 $a_1\sim a_n$，$0 \le a_i \le 1\times 10^9$。 求有多少种 $1\sim n$ 的全排列 $b$，使得对于 $i\in [2,n],a_{b_i}\times a_{b_{i-1}}$ 不是完全平方数。 本题中完 ......

这是一篇简洁易懂的良心题解，提供了多种做法。 对于两个数 $x,y$，定义 $x=n^2 \cdot tx,y=m^2 \cdot ty$。如果 $x\cdot y$ 为平方数，则说明 $tx=ty$。所以我们可以将每个数除去其平方因子，比较相邻两数是否相等即可。 ## F1： 定义 $f_{i,j ......