**補題.**　$k$ を正整数とする．任意の $0$ でない複素数 $e\_1,\ldots,e\_k$ および $0$ でない相異なる複素数 $z\_1,\ldots, z\_k$ に対し，$\displaystyle S(x) := \sum\_{i=1}^k e\_i{z\_i}^x$ は正整数 $x$ に対して恒等的に $0$ になることはない．\
**証明.**　$S(x+1) - z\_k S(x)$ を考えれば，$k$ に関する帰納法で示される．
___
　非負整数 $k$ に対し，数列 $\left\\{ t\_k \right\\}$ を
$$ t\_k := \begin{cases} 0 & (k = 0,1) \\\\ 1 & (k = 2) \\\\ t\_{k-1} + t\_{k-2} + t\_{k-3} & (k \ge 3) \end{cases} $$
で定める．ここで $3$ 次方程式 $x^3 = x^2 + x + 1$ を考えると，これは実数解を $1$ つと $1$ 組の共役な複素数解を持つ．それらを $x=z\_1, z\_2, z\_3$（ただし $z\_1 \in \mathbb R$）とおくと，ある $b\_1, b\_2, b\_3\in\mathbb C$ が存在して，任意の非負整数 $k$ で
$$t\_k = b\_1{z\_1}^k + b\_2{z\_2}^k + b\_3{z\_3}^k$$
と表せる．ここで，$b\_1, b\_2, b\_3$ はいずれも $0$ でない．\
　$\left\\{ t\_k \right\\}$ の定義より，$k = 0, \ldots, n$ について $P\_n(k) = t\_k$ となるから，Lagrange補間より $P\_n(x)$ は
$$
\begin{aligned}
P\_n(x) &=  \sum\_{i=0}^n \mathopen{}\left( t\_i \times \frac{\left(x - 0\right) \times\cdots\times \left(x - (i - 1)\right)}{i!} \times \frac{\left((i + 1) - x\right) \times\cdots\times \left(n - x\right)}{\left(n - i\right) !} \right) \\\\
&= \sum\_{j=1}^3 \mathopen{}\left( b\_j \sum\_{i=0}^n \mathopen{}\left( {z\_j}^i \times \frac{\left(x - 0\right) \times\cdots\times \left(x - (i - 1)\right)}{i!} \times \frac{\left((i + 1) - x\right) \times\cdots\times \left(n - x\right)}{\left(n - i\right) !} \right) \right)
\end{aligned}
$$
と一意に表される．よって二項定理より
$$
\begin{aligned}
a\_n &= \sum\_{j=1}^3 \mathopen{}\left( b\_j \sum\_{i=0}^n \mathopen{}\left( {z\_j}^i \times \frac{\left(n + 1\right) \times\cdots\times \left(n - i + 2\right)}{i!} \times \frac{\left(i - n\right) \times\cdots\times \left(-1\right)}{\left(n - i\right) !} \right) \right) \\\\
&= \sum\_{j=1}^3 \mathopen{}\left( b\_j \sum\_{i=0}^n {z\_j}^i {}\_{n+1}\mathrm C\_i \left(-1\right)^{n-i} \right) = \sum\_{j=1}^3 b\_j \left( {z\_j}^{n+1} - \left(z\_j - 1\right)^{n+1} \right)
\end{aligned}
$$
となり，$k = 1, 2, 3$ に対して $z\_{k+3} = z\_k - 1,\\, d\_k = b\_kz\_k,\\, d\_{k+3} = -b\_{k}z\_{k+3}$ とすれば，以下が成立する．
$$\displaystyle a\_n = \sum\_{i=1}^6 d\_i{z\_i}^n$$
$z\_1,\ldots,z\_6$ は非ゼロで相異なるから，$d\_1,\ldots,d\_6 \ne 0$ も従う．
これが$$\displaystyle a\_{n+m} = \sum\_{i=0}^{m-1} c\_i a\_{n+i}$$をみたすとすると，$g(x)=x^m-\sum\limits\_{i=0}^{m-1} c\_ix^i$ とおけば，代入することで
$$\displaystyle \sum\_{i=1}^6 d\_ig(z\_i)z_i^n=0$$
を得る．すると補題より，任意の $i=1,2,\dots,6$ において $g(z_i)=0$ となるから，$g$ は少なくとも $6$ 次であり，$6$ 次のとき $g$ は一意に決まる．したがって，$m=6$ であり，
$\left(x - z\_1 \right)\left(x - z\_2 \right)\left(x - z\_3 \right) = x^3 - x^2 - x - 1$ より
$$
\begin{aligned}
g(x) &= \left(x - z\_1 \right)\left(x - z\_2 \right)\cdots\left(x - z\_6 \right) \\\\
&= \left( x^3 - x^2 - x - 1 \right) \left( \left(x + 1\right)^3 - \left(x + 1\right)^2 - \left(x + 1\right) - 1 \right) \\\\
&= x^6 + x^5 - 3x^4 -5x^3 + 2x + 2
\end{aligned}
$$
となるから，求める値は $\mathbf{135022}$ である．
公式解説
https://onlinemathcontest.com/contests/omc081/editorial/2518
Lagrange補間を使わないやり方．

---
**補題2．** $n$ を非負整数，$\alpha$ を $1$ でない複素数とする．$n$ 次以下の実係数多項式 $P_n(x)$ が $P_n(k)=\alpha^k$ ($k=0,1,\dots,n$) をみたすとき，以下が成り立つ．$$P_n(n+1)=\alpha^{n+1}-(\alpha-1)^{n+1}.$$

**証明．** $n$ についての帰納法で示す．$n=0$ の場合は明らか．$n\geq 1$ のとき，$$Q_{n-1}(x)=\frac{P_n(x+1)-P_n(x)}{\alpha-1}$$ は $n-1$ 次以下の多項式であり，各 $k=0,1,\dots,n-1$ に対し $Q_{n-1}(\alpha)=\alpha^k$ をみたすから，$Q_{n-1}(x)=P_{n-1}(x)$ である．したがって
$$\\begin{aligned}
P_{n-1}(n)&=\frac{P_n(n+1)-P_n(n)}{\alpha-1},\\\\
P_n(n+1)&=(\alpha-1)(\alpha^{n}-(\alpha-1)^{n})+\alpha^n\\\\
&=\alpha^{n+1}-(\alpha-1)^{n+1}
\\end{aligned}$$
となり，示された．

---

問題の多項式は，$x^3+x^2+x+1$ の根について補題2の多項式を適当に（$0$ でない係数で）線形結合することで得られるから，$a_n$ を $n$ を用いて表せる．あとは本解説と同様である．
ユーザー解説
https://onlinemathcontest.com/contests/omc081/editorial/2518/37
　$n\geq 3$ を整数とします．$n$ 次以下の実数係数多項式 $P\_n(x)$ が
$$P\_n(0) = P\_n(1) = 0,\quad P\_n(2) = 1$$
および
$$ P\_n(k + 3) = P\_n(k + 2) + P\_n(k + 1) + P\_n(k) \qquad (k = 0, 1, \ldots , n - 3) $$
をみたすとき，各 $n$ に対して $P\_n(x)$ が一意に定まります．\
　いま，数列 $\left\\{ a\_n \right\\}\_{n=3,4,\ldots}$ を $a\_n = P\_n(n + 1)$ で定めます．このとき，任意の $n=3, 4, \ldots$ に対して
$$\displaystyle a\_{n+m} = \sum\_{i=0}^{m-1} c\_i a\_{n+i}$$
をみたす実数列 $c\_0, c\_1,\ldots, c\_{m-1}$ が一意に存在するような最小の正整数 $m$ について，以下の値を求めて下さい．
$$\displaystyle\sum\_{i=0}^{m-1} 10^i \left|c\_i\right|$$