本题较难，需要用到偏序集上的容斥原理，以下解答摘译自官方论坛：
先考虑把$n$拆分成$k$个允许相同的正整数乘积的方法数$W'(n,k)$，可以验证$W'$是积性函数。
对$W’$计入的每一种乘积，把其中相同的因子分为一组，就形成$30$的一个加性拆分。
因此先生成$30$的加性拆分，例如$30=a_1+a_2+a_3$，那么就考虑$10000!=m_1^{a_1}m_2^{a_2}m_3^{a_3}$的形式。
显然，一些较大的素因子在$10000!$的质因数分解中仅为一次幂，因此事实上许多拆分是无效的。
对于能满足要求的拆分，再交换素因子尝试将其转换为不同数的乘积，最终结果是$789107601$。
注：因使用sympy求乘法逆以及用到math.prod函数，以下代码为Python 3，运行需要数十分钟但未打印进度，请耐心等待。
import sympy,math
n=10000
k=30
mod=10**9+7
f=[1]
for i in range(1,k+1):
f.append(f[-1]*i)
exponents=[]
for p in sympy.primerange(n+1):
exponents.append(0)
for i in range(p,n+1,p):
while i%p==0:
exponents[-1]+=1
i//=p
m=max(exponents)
cal=lambda c: math.prod(c[i] for i in exponents)%mod
def convolve(tau):
c=[0]*(m+1)
c[0]=1
for t in tau:
while (t < m+1):
for i in range(m,t-1,-1):
c[i]+=c[i-t]
t*=2
return [i%mod for i in c]
d={tuple(): 1}
for i in range(k):
d2={}
for u,v in d.items():
s=[list(u) for _ in u]
for j in range(len(u)):
s[j][j]+=1
s.append([*u,1])
for j in s:
t=tuple(sorted(j))
d2[t]=d2.get(t,0)+v
d=d2
print(sum((-1)**(sum(t)-len(t))*math.prod(f[i-1] for i in t)*v*cal(convolve(t)) for t,v in d.items())*math.prod(sympy.mod_inverse(i,mod) for i in range(2,k+1))%mod)
|
