首先应该注意到尽管n很大，但数组中大多数元素都是1，这是因为若有k个超过1的元素，那么乘积至少是$2^k$，而$2^{30}>10^9$，因此k不会超过29。
接下来就是递归生成满足要求的数组，假设当前数组中最大的数是d，那么可以尝试继续添加$d, d+1, \ldots$，用搜索或递归均可实现。
对每个满足要求的数组，设其长度为k，不同的元素分别有$a_1,\ldots, a_j$个，那么这样的数组总数是多项系数$k!/\prod_{i=1}^{j}a_i!$，阶乘模1234567891的乘法逆可以预处理生成。
最后汇总即得结果$345558983$。
注：因使用sympy计算乘法逆，以下代码为Python 3，运行时间较长（1小时左右）但难以估计进度，需耐心等待。
from sympy import mod_inverse
N=10**9
mod=1234567891
bound=29
r=1
f={}
for i in range(1,N+1):
r=(r*i)%mod
if i <= bound or i>=N-bound:
f[i]=mod_inverse(r,mod)
def cal(m,n,p):
res=f[N-n]
for k in range(p+1,N//m+1):
i=1
x=m*k
while x <= N:
res=(res+f[i]*cal(x,n+i,k))%mod
x*=k
i+=1
if i==2:
break
if p+1 <= N//m and k < N//m:
res=(res+f[N-n-1]*(N//m-k))%mod
return res%mod
print((cal(1,0,1)*r)%mod)
|
