题解

思路

设值 $x$ 在列表中出现 $c_x$ 次。若选择某个不同的质数值 $p$ 作为质因数分解中的底数，就必须消耗它的一次出现；其余恰好 $n$ 个元素作为指数，并按所选的 $n$ 个不同质数底数分配。

固定底数集合 $S$ 后，剩余指数多重集的不同排列数为

$$\frac{n!}{\prod_x(c_x-[x\in S])!} =\frac{n!}{\prod_x c_x!}\prod_{p\in S}c_p.$$

因此只需在所有出现过的不同质数值中选择 $n$ 个，求权值 $c_p$ 的第 $n$ 个基本对称多项式，再乘公共因子 $n!/\prod_x c_x!$。

做法

子任务 1：枚举底数集合与指数排列

枚举所有大小为 $n$ 的不同质数底数集合。删除各底数的一次出现后，对剩余指数多重集做全排列并去重计数。$n\le6$ 时可以直接完成。

子任务 2：枚举质数子集

不同质数值不超过 $24$ 时，深度优先枚举大小为 $n$ 的质数子集，累加所选出现次数之积，再乘公共阶乘因子。

子任务 3：基本对称多项式 DP

令 $dp_j$ 表示已处理若干个不同质数值后，选择恰好 $j$ 个的权值和。遇到出现次数为 $c_p$ 的质数 $p$ 时倒序转移

$$dp_j\leftarrow dp_j+dp_{j-1}c_p.$$

最终答案为

$$dp_n\cdot n!\cdot\prod_x(c_x!)^{-1}.$$

正确性证明

引理 1

任何合法的 $m$ 都对应于从列表中选出 $n$ 个不同质数值作为底数，并把剩余 $n$ 个值作为正指数分配给这些底数。

证明：质因数分解中的底数互不相同且必须是质数。$f(m)$ 共含 $2n$ 个数，所以底数和指数各有 $n$ 个；反过来，任一这样的选择与分配都给出唯一的质因数分解。证毕。

引理 2

固定底数集合 $S$ 时，合法指数分配数为 $n!\prod_{p\in S}c_p/\prod_x c_x!$。

证明：选择底数后，值 $p\in S$ 的剩余次数从 $c_p$ 变为 $c_p-1$，其他值不变。对剩余多重集做排列，数量为 $n!/\prod_x(c_x-[x\in S])!$；利用 $c_p!/(c_p-1)!=c_p$ 化简即得。证毕。

引理 3

DP 结束后，$dp_n=\sum_{|S|=n}\prod_{p\in S}c_p$。

证明：对每个不同质数值分别选择或不选择。倒序转移中的第一项对应不选择，第二项对应选择并乘权值 $c_p$，故按归纳得到所有大小为 $n$ 的集合且各计一次。证毕。

定理

算法输出满足 $f(m)$ 等于给定多重集的正整数个数。

证明：由引理 1，所有合法整数按底数集合唯一分类；引理 2 给出每类的指数分配数；引理 3 对所有底数集合的权值求和。乘公共阶乘因子后恰为全部合法整数数目。证毕。

复杂度

设不同质数值个数为 $q$，最大输入值为 $A$。筛法为 $O(A\log\log A)$，DP 为 $O(nq)$，空间复杂度为 $O(A+n)$。