好久没做题了似乎，最近被抽代虐的有点发慌。

Problem

令 $a_n$ 为 $x^3 - 2^n x^2 + n = 0$ 最大的一个实数根，求

$$\sum_{i=1}^{30} \lfloor {a_i^{987654321}} \rfloor$$

Solution

初看起来不会做……后来一想，指数这么大肯定是有规律的。

对于无理数取整操作来说，比较常用的一种方法是加上一个小于 1 的数，凑成一个整数。要求凑出来的这个整数还是可线性递推求出来的。在这个题目中，把这个方程的几个根打出来看看就会发现一个根很大（理性可以感受到是 $2^n$ 左右的），另外两个根非常小，绝对值都小于 1 。

对于 $n$ ，我们不妨设三个根分别为 $a, b, c$ 。一种很自然的想法就是考虑 $S_k = a^k + b^k + c^k$ 是否是整数以及是否可递推。递推公式很明显：

$$S_{k+1} = 2^n S_k - n S_{k - 2}$$

现在考虑是否为整数的问题。我们只需考虑 $S_0, S_1, S_2$ 就好了。显然 $S_0 = 3$ 。由于 $a, b, c$ 是方程的三个根，可以得到 $(x - a)(x - b)(x - c) = x^3 - 2^n x^2 + n$ ，展开得到 $a + b + c = 2^n, ab + bc + ca = 0$ 。所以 $S_1 = 2^n, S_2 = S_1^2 - 2(ab + bc + ca) = 4^n$ ，都是整数。

然后，矩阵乘法就交给 sage 吧～

@dyh 你对 438 有啥想法吗……