题目描述

群里有 $k$ 个不同的复读机

为了庆祝平安夜的到来，在接下来的 $n$ 秒内，它们每秒钟都会选出一位优秀的复读机进行复读

非常滑稽的是，一个复读机只有总共复读了 $d$ 的倍数次才会感到快乐

问有多少种不同的安排方式使得所有的复读机都感到快乐

其中 $1 \le n \le 10^9, 1 \le k \le 500000, 1 \le d \le 3$，答案模 $19491001$

题解

~~说到 19491001，我就想起了 19 学竞赛，49 入国军~~

若 $d=1$，则答案就是：

$$
k^n
$$

若 $d=2$，则答案就是：

$$
\begin{aligned}
&\left( \sum_{i \ge 0} [2|i] \frac{x^i}{i!} \right)^k[x^n]n! \\
=&\left( \frac{e^x+e^{-x}}{2} \right)^k[x^n]n! \\
=&\sum_{i=0}^{k} {k \choose i} \frac{1}{2^k} e^{xi-x(k-i)}[x^n]n! \\
=&\sum_{i=0}^{k} {k \choose i} \frac{1}{2^k} e^{x(2i-k)}[x^n]n! \\
=&\sum_{i=0}^{k} {k \choose i} \frac{(2i-k)^{n}}{2^k}
\end{aligned}
$$

若 $d=3$，则答案就是：

$$
\begin{aligned}
&\left( \sum_{i \ge 0} [3|i] \frac{x^i}{i!} \right)^k[x^n]n! \\
=&\left( \frac{1}{3}\sum_{i \ge 0} \frac{x^i}{i!} \sum_{j=0}^{2}\omega_3^{ij} \right)^k[x^n]n! \\
=&\left( \frac{1}{3}\sum_{i \ge 0} \frac{x^i+(x\omega_3)^i+(x\omega_3^2)^i}{i!} \right)^k[x^n]n! \\
=&\left(\frac{e^x+e^{\omega_3x}+e^{\omega_3^2x}}{3}\right)^k [x^n]n! \\
=&\frac{1}{3^k}\sum_{i+j \le k} {k \choose i} {k-i \choose j} e^{xi+x\omega_3j+x\omega_3^2(k-i-j)} [x^n]n! \\
=&\frac{1}{3^k}\sum_{i+j \le k} {k \choose i} {k-i \choose j} (i+\omega_3j+\omega_3^2(k-i-j))^n \\
\end{aligned}
$$