题解：P5947 [POI 2003] Trinomial

· · 题解

题意：

求 (x^2+x+1)^n 的第 i 项系数。

思路：

看到这种 n 次幂求系数应该很好想到二项式定理吧？

注意到唐诗作者没读完题一直想着怎么把 3x 消掉

二项式定理：

(x+y)^n=\sum_{i=1}^{n}C_n^i x^i y^{n-i}

所以这道题想着怎么把 x^2+x+1 变成一次多项式

注意到题目说对 3 取模，所以想办法把其中的东西凑成三的倍数消掉。

所以我们可以开始推式子：

x^2+x+1=(x^2-2x+1)+3x=(x-1)^2+3x

我们应该开始用二项式定理了。

从前面的推式子中，我们把原式可以推成这样：

(x^2+x+1)^n=\sum_{i=1}^n C_n^i(x-1)^{2i}(3x)^{n-i}

很显然，只要后面那个 (3x)^{n-i} 存在，那么这一项就会被模三的输出要求搞没，那么这一项就将没有意义。

所以我们考虑没有这一项的情况（很容易看出吧？就是 n-i=0 时），那么这个肥大的式子，就被我们变成了这样：

\sum_{i=1}^n C_n^i(x-1)^{2i}(3x)^{n-i}=C_n^n(x-1)^{2n}=(x-1)^{2n}(mod 3)

接下来就是比较裸的二项式定理了，哦对了，这道题 n 很大，所以请使用 lucas 定理