[ARC062E] Building Cubes with AtCoDeer

题意

给定 \(n\) 个正方形，每个正方形的四个角有颜色，有方向。

你需要选出 \(6\) 个正方形，拼出一个正方体，使得角上的颜色相同。

问有多少种方案。

\(n \le 400, m \le 1000\)

Sol

注意到若确定了对着的两个面，就可以确定正方体上所有面的颜色。

因此考虑枚举两个面，计算出 \(8\) 个角的颜色。

算出每个位置可以放多少个可以简单的用 \(\texttt{Trie}\) 求出。

现在问题变成知道 \(4\) 个面分别有多少种方案，求总方案数。

乍一看难以去重，不对每个给定的正方形考虑难以做出。

但是不难发现若一个位置可以同时放置两个或多个正方形，那么显然这两个正方形是完全相同的。

因此无论选择哪一个，都会使得下一个位置可以放置的数量 \(-1\)，这显然是确定的。

所以直接对于选择的所有情况减掉贡献，就做完了。

复杂度 \(O(4 ^ 3 n ^ 2)\)。