题目大意
(n)个不同的球放入(k)个不同的盒子里，每个盒子里的球数都是(d)的倍数，求方案数(\%19491001)的值
subtask1(5pts): (d=1)
subtask2(25pts): (nleq 10^3,kleq 100)
subtask3(30pts): (nleq 10^9,kleq 5*10^5,d=2)
subtask4(40pts): (nleq 10^9,kleq 10^3,d=3)
题解
(O(nk))暴力dp：
[f_{i,j}*(x*d)! -> f_{i+1,j+x*d}\
ans=frac{f_{k,n}}{n!}
]
可以写成(k)个同样的多项式相乘（最后再除个(n!)），写出生成函数：
[egin{aligned}
F&=sum_{i=0}^infty [d|i] frac{1}{i!} x^i\
&=sum_{i=0}^infty frac{1}{d}(sum_{j=0}^{d-1} omega_d^{ij}) frac{x^i}{i!}\
&=frac{1}{d} sum_{i=0}^{d-1} sum_{j=0}^infty (omega_d^i)^j frac{x^j}{j!}\
&=frac{1}{d} sum_{i=0}^{d-1} e^{omega_d^ix}\
end{aligned}
]
求这个东西的(k)次方可以二（?）项式定理展开一下。
[egin{aligned}
F^k&=frac{1}{d^k} sum_{a_1+a_2+...a_d=k} frac{k!prod_{i=0}^{d-1} e^{a_iomega_d^ix}}{prod_{i=0}^{d-1} a_i!}\
F^k&=frac{1}{d^k} sum_{sum a_i=k} frac{k! e^{xsum_{i=0}^{d-1} a_iomega_d^i}}{prod a_i!}\
d^kF^k&=sum_{sum a_i=k} frac{k!sum_{j=0}^infty frac{x^j}{j!} (sum_{i=0}^{d-1} a_iomega_d^i)^j}{prod a_i!}\
frac{d^kF^k}{k!}&=sum_{j=0}^infty frac{x^j}{j!} sum_{sum a_i=k} frac{(sum_{i=0}^{d-1} a_iomega_d^i)^j}{prod a_i!}\
ans=frac{F^k(n)}{n!}&=frac{k!}{d^k} sum_{sum a_i=k} frac{(sum_{i=0}^{d-1} a_iomega_d^{i})^n}{prod a_i!}
end{aligned}
]
复杂度大约(O(k^{d-1}))
对于(d=1)
[ans=k^n
]
对于(d=2)
[ans=frac{k!}{2^k} sum_{i=0}^k frac{(2i-k)^n}{i!(k-i)!}
]
对于(d=3)
[ans=frac{k!}{3^k} sum_{i=0}^k sum_{j=0}^{k-i} frac{(omega_3*i+omega_3^2*j+k-i-j)^n}{i!j!(k-i-j)!}
]
(19491000)是(6)的倍数，所以单位根存在。