复健

可以发现数列中非 $1$ 的元素个数不可能超过 $\log_2 k$ 个。用 $dp[i][j]$ 表示长度为 $i$ 的只含有 $2\sim k$ 之间的数的序列乘积为 $j$ 的方案数。则我们要求乘积为 $x$ 的答案，方案数为 $\displaystyle\sum_{u=1}^{n}dp[u][x]\sum_{v=0}^{n-u}C(u+v,u)$，其中 $\displaystyle\sum_{v=0}^{n-u}C(u+v,u)=\sum_{v=0}^{n-u}C(u+v+1,u+1)-C(u+v,u+1)=C(n+1,u+1)$。

注意 $u$ 只能取 $[1,\log_2 k]$，所以总复杂度为 $O(k\log_2^2 k)$。