(d=1),那么任何时刻都可以(k)个复读机的一种,答案为(k^n)
(d>1),可以枚举某个复读机的复读次数(必须是(d)的倍数),然后第(i)个复读时间为(x_i),那么答案为(n!sumlimits_{d|x_i,sum x_i=n} prod frac{1}{x_i!}),这个显然可以暴力背包生成函数,因为有(d|x_i)的限制,那么可以套用单位根反演,单个复读机的生成函数为(sum_{i=0}^{infty}[d|i]frac{x^i}{i!}),也就是
[frac{1}{d}sum_{i=0}^{infty}sum_{j=0}^{d-1}omega_{d}^{ij}frac{x^i}{i!}
]
[frac{1}{d}sum_{j=0}^{d-1}sum_{i=0}^{infty}frac{omega_{d}^{ij}x^i}{i!}
]
[frac{1}{d}sum_{i=0}^{d-1}e^{omega_{d}^{i}x}
]
然后求出这个生成函数的(k)次方的(n)次项系数乘上(n!)就好了(注意到(n!)会和(n)次项中的(frac{1}{n!})抵消),实现的时候把(e^x)看成未知数,枚举(e^{omega_{d}^{0}x},e^{omega_{d}^{1}x},(d=3)时有(e^{omega_{d}^{2}x}))出现了多少次,然后系数乘上组合数即可(说白了就是二项式定理展开)