UOJ450 复读机

题意

$k$ 种球，每种个数必须是 $d$ 的倍数，共 $n$ 个，求排成一行的方案数.

$n\le 10^9, k\le 5\times10^5, d\le 3$，答案对 $19491001$ 取模.

题解

$$\begin{aligned} \text{Ans}&=n!\sum_{i_1 \ge 0,d\mid i_1}\frac{1}{i_1!}\sum_{0\le i_2,d\mid i_2}\frac{1}{i_2!}\cdots\sum_{0\le i_k,d\mid i_k}\frac{1}{i_k!}\\ &=[x^n]n!(\sum_{i\ge 0,d\mid i}\frac{x^i}{i!})^k\\ \end{aligned}$$

$$\begin{aligned} \sum_{i\ge 0,d\mid i}\frac{x^i}{i!}&=\sum_{i\ge 0}\frac{x^i}{i!}\frac{1}{d}\sum_{0\le j < d}{\omega_d^j}^i& \text{单位根反演}\\ &=\frac{1}{d}\sum_{0\le j < d}\sum_{i\ge 0}\frac{(x\omega_d^j)^i}{i!}\\ &=\frac{1}{d}\sum_{0\le j < d}e^{x\omega_d^j}& \text{泰勒展开}\\ \end{aligned}$$

$d=2$：

$$\begin{aligned} \sum_{i\ge 0,d\mid i}\frac{x^i}{i!}&=\frac{1}{d}\sum_{0\le j < d}e^{x\omega_d^j}\\ &=\frac{e^x+e^{-x}}{2}\\ (\sum_{i\ge 0,d\mid i}\frac{x^i}{i!})^k&=n!(\frac{e^x+e^{-x}}{2})^k\\ &=\frac{1}{2^k}\sum_{0\le i\le k}\begin{pmatrix}k\\i\end{pmatrix}e^{ix}e^{-x(k-i)} & \text{二项式定理}\\ &=\frac{1}{2^k}\sum_{0\le i\le k}\begin{pmatrix}k\\i\end{pmatrix}e^{2ix-kx}\\ \text{Ans}&=[x^n]n!(\sum_{i\ge 0,d\mid i}\frac{x^i}{i!})^k\\ &=\frac{n!}{2^k}\sum_{0\le i\le k}\begin{pmatrix}k\\i\end{pmatrix}[x^n]e^{2ix-kx}\\ &=\frac{n!}{2^k}\sum_{0\le i\le k}\begin{pmatrix}k\\i\end{pmatrix}\frac{(2i-k)^n}{n!} & \text{泰勒展开}\\ &=\frac{1}{2^k}\sum_{0\le i\le k}\begin{pmatrix}k\\i\end{pmatrix}(2i-k)^n \end{aligned}$$ $d=3$： $$\begin{aligned} \sum_{i\ge 0,d\mid i}\frac{x^i}{i!}&=\frac{1}{d}\sum_{0\le j < d}e^{x\omega_d^j}\\ &=\frac{e^x+e^{\omega_3x}+e^{\omega_3^2x}}{3}\\ (\sum_{i\ge 0,d\mid i}\frac{x^i}{i!})^k&=n!(\frac{e^x+e^{\omega_3x}+e^{\omega_3^2x}}{3})^k\\ &=\frac{1}{3^k}\sum_{0\le i\le k}\begin{pmatrix}k\\i\end{pmatrix}\sum_{0\le j\le k-i}\begin{pmatrix}k-i\\j\end{pmatrix}e^{ix}e^{j\omega_3x}e^{(k-i-j)\omega_3^2x} & \text{多项式定理}\\ &=\frac{1}{3^k}\sum_{0\le i\le k}\sum_{0\le j\le k-i}\begin{pmatrix}k\\i\end{pmatrix}\begin{pmatrix}k-i\\j\end{pmatrix}e^{ix+j\omega_3x+k\omega_3^2x-i\omega_3^2x-j\omega_3^2x}\\ \text{Ans}&=[x^n]n!(\sum_{i\ge 0,d\mid i}\frac{x^i}{i!})^k\\ &=\frac{n!}{3^k}\sum_{0\le i\le k}\sum_{0\le j\le k-i}\begin{pmatrix}k\\i\end{pmatrix}\begin{pmatrix}k-i\\j\end{pmatrix}[x^n]e^{ix+j\omega_3x+k\omega_3^2x-i\omega_3^2x-j\omega_3^2x}\\ &=\frac{n!}{3^k}\sum_{0\le i\le k}\sum_{0\le j\le k-i}\begin{pmatrix}k\\i\end{pmatrix}\begin{pmatrix}k-i\\j\end{pmatrix}\frac{(i+j\omega_3+k\omega_3^2-i\omega_3^2-j\omega_3^2)^n}{n!} & \text{泰勒展开}\\ &=\frac{1}{3^k}\sum_{0\le i\le k}\sum_{0\le j\le k-i}\begin{pmatrix}k\\i\end{pmatrix}\begin{pmatrix}k-i\\j\end{pmatrix}(i+j\omega_3+k\omega_3^2-i\omega_3^2-j\omega_3^2)^n \end{aligned}$$