EGF：\(G(x)=\sum\limits_{i}[d|i]\frac{x^i}{i!}\)
\(d=2\)时：\(G(x)=\frac{e^{x}+e^{-x}}{2}\)，\(G(x)^k[x^n]\)可以二项式定理后把每个项算\([x^n]\)
\(d=3\)时：\(G(x)=\sum\limits_{i}[d|i]\frac{x^i}{i!}=\frac{1}{d}\sum\limits_{i}\sum\limits_{j=0}^{d-1}\omega_d^{ij}\frac{x^i}{i!}=\frac{1}{d}\sum\limits_{j=0}^{d-1}e^{\omega_d^j\cdot x}\)
\(Ans=n!\frac{1}{d^k}(\sum\limits_{j=0}^{d-1}e^{\omega_d^j\cdot x})^k\)，由于\(k\le 1000,d=3\)，可以枚举\(e^{\omega_3^0\cdot x},e^{\omega_3^1\cdot x},e^{\omega_3^2\cdot x}\)的个数
原文：https://www.cnblogs.com/Grice/p/12822877.html