P2012 拯救世界2 题解

· · 题解

本题解主要说优化，其它就不详细说明了，别的题解有很多讲解了。

思路:看到这道题后，很明显会想到指数型生成函数 \operatorname{EGF}，因为我们需要考虑顺序(题目里要求的是序列的个数而不是集合)。

我们只要求出三个限制的 \operatorname{EGF} 再相乘，然后取其 n 次项系数，最后与 n! 相乘。

众所周知，根据泰勒展开，e^{cx}=\sum_{i=0}^{\infty}c^i\frac{x^i}{i!}。

所以它们的 \operatorname{EGF} 分别为 e^{4x},\frac{(e^x+e^{-x})^4}{16},\frac{(e^x-e^{-x})^4}{16}(每种都有四个所以要四次方)。

然后取其 n 次项系数，并与 n! 相乘(手算时建议用泰勒展开)。

最后答案就是 \frac{12^n-4\times8^n+6\times4^n+(-4)^n}{256}。

但我们发现 256 和 1000000000 有不互质，所以 256 没有逆元。

没办法，这能怪出题人太毒瘤。

我们发现，这个式子可以写成 81\times12^{n-4}-8^{n-2}+6\times4^{n-4}+{(-4)}^{n-4}。

但 n<4 怎么办?

我们发现，如果 n<4，那么一定没有解决方案，因为乾、坎、艮、震一定要出现奇数次，所以最少也要 n=4 才能有解。

后来试了一下，这里其实不用优化也能过，但还是讲讲各种优化的方法。

优化0 不优化

最大耗时点 813ms。

优化1 卡常(就是吸了个氧)

这里好像加快读会出问题。

吸氧以后最大耗时 738ms。

因为是用 while 做循环所以开不开 register 都一样。

优化2 指数化简

根据 n \bmod 2 分类讨论，再用 2^{n-4} 和 3^{n-4} 表示整个式子就会快很多。

指数化简后(没吸氧) 440ms，吸氧后 394ms

优化3 指数取模

因为 \varphi{(1000000000)}=400000000。

如果指数大于 400000000 ，只要在快速幂前把指数模 400000000 再加 400000000 就可以啦。

化简后 398ms，加上指数化简并且吸氧 203ms。

优化4 光速幂

大家都知道，懒得写也不说了。

最后

代码不贴了，其它题解已经有很多了。

第一次写黑题解，请管理大大多多包含。