容易看出
\begin{align*}
g(-1)&=-1-2^n+n < 0
g(0)&=n>0
g(1)&=1-2^n+n\le 0
g(2^n)&=n>0
\end{align*}
因此由介值性可得g有三个实根，且若这三个根分别是$x_1 < x_2 < x_3$，那么$x_1$在-1到0之间，$x_2$在0到1之间，$x_3$在1到$2^n$之间。
取一些具体的n可以观察到当n增加时，$x_3$以很快的速度接近$2^n$，且由$x_1+x_2+x_3=2^n$可知$|x_2|>|x_1|$，但$|x_2|-|x_1|$很接近0。
考虑矩阵
$$A_n=\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ -n & 0 & 2^n \end{pmatrix},$$
它的特征多项式就是$g(x)$，从而$x_1^k+x_2^k+x_3^k=\tr(A_n^k)$，其中$\tr$是矩阵的迹。
当$k=987654321$时$|x_1^k|$和$|x_2^k|$都非常小，且后者略大于前者，因此
$$\lfloor x_3^{987654321}\rfloor=\tr(A_n^{987654321})-1.$$
用矩阵快速幂计算后者并汇总即得最终结果$28010159$。
mul=lambda A,B: [[sum(A[i][k]*B[k][j] for k in range(3))%(10**8) for j in range(3)] for i in range(3)]
tr=lambda A: A[0][0]+A[1][1]+A[2][2]
def pow(A,n):
if n==1:
return A
if n==2:
return mul(A,A)
B=pow(A,n//2)
return mul(B,B) if n%2==0 else mul(mul(B,B),A)
print sum(tr(pow([[0,1,0],[0,0,1],[-i,0,1 << i]],987654321))-1 for i in range(1,31))%(10**8)
|
