P2012 拯救世界2

· · 个人记录

因为是排成序列，所以方案是**有序**的，因此使用 $\text{EGF}$。 没有限制的基因：$\sum_{i=0}^{\infty}\dfrac{x^i}{i!}=e^x

奇数：\sum_{i=0}^{\infty}\dfrac{x^{2i+1}}{(2i+1)!}=\dfrac{e^x-e^{-x}}{2}

偶数：\sum_{i=0}^{\infty}\dfrac{x^{2i}}{(2i)!}=\dfrac{e^x+e^{-x}}{2}

所以答案等于

[\dfrac{x^n}{n!}](\dfrac{e^x+e^{-x}}{2})^4(\dfrac{e^x-e^{-x}}{2})^4(e^x)^4

我们进行一个暴力展开：

[\dfrac{x^n}{n!}]\dfrac{e^{12x}-4e^{8x}+6e^{4x}-4e^{0x}+e^{-4x}}{256}

于是等于

\dfrac{12^n-4*8^n+6*4^n+(-4)^n}{256}

但是模数是 10^9，256 没有逆元。

因此暴力除掉以后就是

81*12^{n-4}-64*8^{n-4}+6*4^{n-4}+(-4)^{n-4}