解题思路

本题要求用给定的木棍拼出一个正多边形的方案数。根据正多边形的定义，每个正多边形的边数 $k$ 必须满足所有边的长度相等，因此需要统计每个长度出现的次数，并计算对于每个 $k$ 能够组成正 $k$ 边形的方案数。方案数等于所有长度中出现次数 $c \geq k$ 的组合数 $C(c, k)$ 之和。

解题步骤

1. 统计频率：使用哈希表统计每个长度出现的次数。
2. 预处理阶乘和逆元：为了快速计算组合数 $C(n, k)$，预处理阶乘数组 fact 和其逆元数组 inv_fact。

题目内容

Zeeman 有 $3≦n≦5×10^3$ 根木棍，其中第 $i$ 根木棍的长度为 $1≦a_i≦ 10^9$ 。

Zeeman 想知道，用这些木棍(不可合并与分割)拼出一个正多边形有多少种方案。